-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathbuddyStrings.java
More file actions
88 lines (70 loc) · 2.8 KB
/
buddyStrings.java
File metadata and controls
88 lines (70 loc) · 2.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
import java.util.*;
public class buddyStrings {
public static boolean buddyStrings(String s, String goal) {
// 1. test they are the same length
// 2. if A==B, if there are repeated chars, return true
// 3. else count number of differences; if there are only 2
// AND the strings are equal after swap, return tru
// 1.
if (s.length() != goal.length()) return false;
// 2.
if (s.equals(goal)) {
for (int i = 0; i < s.length(); i++) {
// looks for the char at i, and
// java lastIndexOf = last ind of the char at i
// this says the last ind of char at i is not i; there's another
if (s.lastIndexOf(s.charAt(i)) != i) {
return true;
}
}
return false;
}
// 3.
int diffCount = 0;
int[] diffIndicies = new int[2];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != goal.charAt(i)) {
if (diffCount == 2) return false;
diffIndicies[diffCount] = i;
diffCount++;
System.out.println("27i: " + i);
}
}
if (diffCount != 2) return false;
return (s.charAt(diffIndicies[0]) == goal.charAt(diffIndicies[1])
&& s.charAt(diffIndicies[1]) == goal.charAt(diffIndicies[0]));
}
public static void main(String[] args) {
String s = "aaaaaaabc";
String goal = "aaaaaaacb";
System.out.println("Output: " + buddyStrings(s, goal));
}
}
/*
solution passes
space: O(1); created diffIndices array fixed at 2 and does not depend on
s and goal
time: O(n);worst case will iterate through s and goal twice:
1. checking for repeated chars in s
2. once comparing characters betweeen s and goal
Depends on length of s/goal
* https://leetcode.com/problems/buddy-strings/
* Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.
Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].
For example, swapping at indices 0 and 2 in "abcd" results in "cbad".
Example 1:
Input: s = "ab", goal = "ba"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'b' to get "ba", which is equal to goal.
Example 2:
Input: s = "ab", goal = "ab"
Output: false
Explanation: The only letters you can swap are s[0] = 'a' and s[1] = 'b', which results in "ba" != goal.
Example 3:
Input: s = "aa", goal = "aa"
Output: true
Explanation: You can swap s[0] = 'a' and s[1] = 'a' to get "aa", which is equal to goal.
Constraints:
1 <= s.length, goal.length <= 2 * 104
s and goal consist of lowercase letters.
*/