LeetCode 859. Buddy Strings

Question

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: A = "ab", B = "ba"
Output: true

Input: A = "ab", B = "ab"
Output: false

Input: A = "aa", B = "aa"
Output: true

Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true

Input: A = "", B = "aa"
Output: false

Solution

The first method in my mind is to iterate different pair in String A and then exchange, and to see if it equals to B. Of course, this approach would be TLE, due to the time complexity is O(n^2). So, when I look the test case carefully, especially ths test case ofA: aa, B: aa. So, we have to compare to see if A and B equals.

Code

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
// time:O(n) space:O(1)
public boolean buddyStrings(String A, String B) {
if (A.length() != B.length()) return false;
if (A.equals(B)) {
// case "aa" "aa";
int[] count = new int[26];
for (char ch : A.toCharArray()) count[ch - 'a']++;
for (int c : count) if (c > 1) return true;
return false;
} else {
int first = -1, second = -1;
for (int i = 0; i < A.length(); i++) {
if (A.charAt(i) != B.charAt(i)) {
if (first == -1)
first = i;
else if (second == -1)
second = i;
else
return false;
}
}
return second != -1 &&
A.charAt(first) == B.charAt(second) &&
A.charAt(second) == B.charAt(first);
}
}