[leetcode] 859. 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:

1. 0 <= A.length <= 20000
2. 0 <= B.length <= 20000
3. A and B consist only of lowercase letters.

分析

• 這是一道easy類型的題目，開始大家可能都覺得這是一道dp的問題，其實簡單解法既可以，廢話不多說，直接看代碼。
• 如果字元串A與字元串B不相等，則直接傳回false；然後周遊字元串A，B，記錄字元串中字元不相等的位置，然後把上面例子的五種情況都考慮到就行了。

代碼

class Solution {
public:
    bool buddyStrings(string A, string B) {
        int m=A.length();
        int n=B.length();
        if(m!=n){
            return false;
        }
        int pos=-1;
        bool isSwap=false;
        bool isRepeat=false;
        vector<int> count(26,0);
        for(int i=0;i<m;i++){
            if(A[i]!=B[i]){
                if(pos==-1){
                    pos=i;
                }else if(isSwap||A[pos]!=B[i]||A[i]!=B[pos]){
                    return false;
                }else{
                    isSwap=true;
                }
            }
            if(++count[A[i]-'a']>1) isRepeat=true;
        }
        return isSwap||isRepeat;
    }
    
};      

參考文獻