[LeetCode October Challange] Day 12 - Buddy Strings

Given two strings A and B of lowercase letters, return true if you can swap two letters in A so the result is equal to B, 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 A[i] and A[j]. For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: A = "ab", B = "ba"
Output: true
Explanation: You can swap A[0] = 'a' and A[1] = 'b' to get "ba", which is equal to B.

Example 2:

Input: A = "ab", B = "ab"
Output: false
Explanation: The only letters you can swap are A[0] = 'a' and A[1] = 'b', which results in "ba" != B.

Example 3:

Input: A = "aa", B = "aa"
Output: true
Explanation: You can swap A[0] = 'a' and A[1] = 'a' to get "aa", which is equal to B.

Example 4:

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

Example 5:

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

Constraints:

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

---

Solution

Time complexity : O(n)
Space complexity : O(1)

class Solution {
public:
    bool buddyStrings(string A, string B) {
        if (A.size() != B.size()) return false;
        int a_cnt[26] = {0}, b_cnt[26] = {0};
        int diff = 0;
        for (int i=0; i<A.size(); ++i) {
            if (A[i]!=B[i] && ++diff>2) return false;
            ++a_cnt[A[i]-'a'];
            ++b_cnt[B[i]-'a'];
        }
        for (int i=0; i<26; ++i) {
            if (0==diff && a_cnt[i]>1) return true;
            if (a_cnt[i] != b_cnt[i]) return false;
        }
        return 2 == diff;
    }
};

根據題目表示，buddy string的性質為：

1. 長度相同。
2. 不相同之處為2，且各字母出現的頻率相同。
3. 不相同之處為0，有其中一字母出現的頻率為2以上。

先比較長度。
統計不相同之處和各字母出現頻率。
檢查各字母出現的頻率。
檢查不相同之處。