LeetCode-Buddy Strings

Description：

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:

Input: A = "ab", B = "ba"
Output: true      

Example 2:

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

Example 3:

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

Example 4:

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

Example 5:

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

Note:

• 0 <= A.length <= 20000
• 0 <= B.length <= 20000
• A and B consist only of lowercase letters.

題意：給定兩個字元串A和B，判斷能夠将A中的兩個字元交換使得A與B相等；

Java

class Solution {
    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length()) {
            return false;
        }
        for (int i = 0; i < A.length() - 1; i++) {
            for (int j = i + 1; j < A.length(); j++) {
                StringBuilder sb = new StringBuilder(A);
                sb.replace(i, i + 1, "" + A.charAt(j));
                sb.replace(j, j + 1, "" + A.charAt(i));
                if (sb.toString().equals(B)) {
                    return true;
                }
            }
        }
        return false;
    }
}      

• 第一種如果A.equals(B)，要相令A交換兩個字元後還是與B相等，那麼A中至少有一個字元出現兩次，這樣交換前後A不變
• 第二種如果A與B不相等，那麼我們就可以找到A中從首部開始出現的第一個與B相同位置但不相等的字元（即A[i] != B[i], 0 <= i < A.length()）；之後，我們需要從這個位置往後找出A中與B[i]相等的字元進行交換（即A[j] == B[i], i < j < A.length()），判斷交換後是否相等，一直到判斷完所有這個位置之後A中與B[i]相等的字元；

Java

class Solution {
    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length() || A.length() == 0) {
            return false;
        }
        if (A.equals(B)) {
            int[] letter = new int[26];
            for (int i = 0; i < A.length(); i++) {
                letter[A.charAt(i) - 'a'] += 1;
                if (letter[A.charAt(i) - 'a'] > 1) return true;
            }
            return false;
        }
        int index = 0;
        while (index < A.length() && A.charAt(index) == B.charAt(index)) {
            index++;
        }
        for (int i = index + 1; i < A.length(); i++) {
            if (A.charAt(i) == B.charAt(index)) {
                StringBuilder sb = new StringBuilder(A);
                sb.replace(index, index + 1, "" + A.charAt(i));
                sb.replace(i, i + 1, "" + A.charAt(index));
                if (sb.toString().equals(B)) {
                    return true;
                }
            }
        }
        return false;
    }
}