Leetcode859.Buddy Strings亲密字符串

给定两个由小写字母构成的字符串 A 和 B ，只要我们可以通过交换 A 中的两个字母得到与 B 相等的结果，就返回 true ；否则返回 false 。

示例 1：

输入： A = "ab", B = "ba" 输出： true

示例 2：

输入： A = "ab", B = "ab" 输出： false

示例 3:

输入： A = "aa", B = "aa" 输出： true

示例 4：

输入： A = "aaaaaaabc", B = "aaaaaaacb" 输出： true

示例 5：

输入： A = "", B = "aa" 输出： false

提示：

0 <= A.length <= 20000
0 <= B.length <= 20000
A 和 B 仅由小写字母构成。

暴力法超时：

class Solution {

public:

    bool buddyStrings(string A, string B) {

        int len1 = A.size();

        int len2 = B.size();

        if(len1 <= 1 || len2 <= 1 || len1 != len2)

            return false;

        for(int i = 0; i < len1; i++)

        {

            for(int j = i + 1; j < len1; j++)

            {

                swap(A[i], A[j]);

                if(A == B)

                    return true;

                else

                    swap(A[i], A[j]);

            }

        }

        return false;

    }

};

官方题解：

方法：情况列举

思路

如果 A[i] == B[i]，我们就说 i 是匹配的，否则称 i 是不匹配的。亲密字符串几乎是完全匹配的，因为一次交换只会影响到两个索引。

如果交换 A[i] 和 A[j] 可以证明 A 和 B 是亲密字符串，那么就有 A[i] == B[j] 以及 A[j] == B[i]。这意味着在 A[i], A[j], B[i], B[j] 这四个自由变量中，只存在两种情况：A[i] == A[j] 或 A[i] != A[j]

算法

让我们来看看这些情况。

在 A[i] == A[j] == B[i] == B[j] 的情况下，字符串 A 与 B 相等。因此，如果 A == B，我们应当检查每个索引 i 以寻找具有相同值的两个匹配。

在 A[i] == B[j], A[j] == B[i], (A[i] != A[j]) 的情况下，其余索引是相匹配的。所以如果 A 和 B 只有两个不匹配的索引（记作 i 和 j），我们应该检查并确保等式 A[i] == B[j] 和 A[j] == B[i] 成立。

class Solution {

public:

    bool buddyStrings(string A, string B) {

        int len1 = A.size();

        int len2 = B.size();

        if(len1 != len2 || len1 <= 1 || len2 <= 1)

            return false;

        if(A == B)

        {

            map<char, int> check;

            for(int i = 0; i < len1; i++)

                check[A[i]]++;

            for(map<char, int> :: iterator itr = check.begin(); itr != check.end(); itr++)

            {

                if(itr ->second >= 2)

                    return true;

            }

            return false;

        }

        else

        {

            int first = -1;

            int second = -1;

            for(int i = 0; i < len1; i++)

            {

                if(A[i] != B[i])

                {

                    if(first == -1)

                    {

                        first = i;

                    }

                    else if(second == -1)

                    {

                        second = i;

                    }

                    else

                        return false;

                }

            }

            if(first != -1 && second != -1 && A[first] == B[second] && A[second] == B[first])

                return true;

            else

                return false;

        }

    }

};

巴特西

Leetcode859.Buddy Strings亲密字符串

最新文章

热门文章