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);
        }
    }