C#LeetCode刷题之#859-亲密字符串（Buddy Strings）

问题

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

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

输出： true

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

输出： false

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

输出： true

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

输出： true

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

输出： false

提示：

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

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.

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

Note:

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

示例

public class Program {

    public static void Main(string[] args) {

        var A = "aaaaaaabc";

        var B = "aaaaaaacb";

        var res = BuddyStrings(A, B);

        Console.WriteLine(res);

        A = "ab";

        B = "ab";

        res = BuddyStrings2(A, B);

        Console.WriteLine(res);

        Console.ReadKey();

    }

    private static bool BuddyStrings(string A, string B) {

        //暴力求解，LeetCode超时未AC

        if(A.Length != B.Length) return false;

        var sb = new StringBuilder(A);

        //逐一测试所有字符

        for(var i = 0; i < A.Length; i++) {

            for(var j = i + 1; j < A.Length; j++) {

                var swap = sb[i];

                sb[i] = sb[j];

                sb[j] = swap;

                //相同时，返回 true

                if(sb.ToString() == B) return true;

                //重置 sb

                sb = new StringBuilder(A);

            }

        }

        //返回 false

        return false;

    }

    private static bool BuddyStrings2(string A, string B) {

        //长度不同时，直接返回 false

        if(A.Length != B.Length) return false;

        //用 list 统计相同位置处字符不同的索引值

        var list = new List<int>();

        for(var i = 0; i < A.Length; i++) {

            if(A[i] != B[i]) list.Add(i);

            if(list.Count > 2) break;

        }

        //若所有位置字符相

        //那么若原字符串包含相同的字符则为亲密字符串

        if(list.Count == 0) {

            if(ContainsSameLetter(A)) return true;

        }

        //不等于 2，则没有办法通过交换获得相同结果

        if(list.Count != 2) return false;

        //用 sb 交换 2 个值

        var sb = new StringBuilder(A);

        var swap = sb[list[0]];

        sb[list[0]] = sb[list[1]];

        sb[list[1]] = swap;

        //相同时，返回 true

        return sb.ToString() == B;

    }

    private static bool ContainsSameLetter(string A) {

        //哈希法判定是否存在相同字符

        var dic = new Dictionary<char, int>();

        foreach(var c in A) {

            if(dic.ContainsKey(c)) {

                dic[c]++;

            } else {

                dic[c] = 1;

            }

        }

        //包含2个及以上的数量即存在相同字符

        return dic.Where(c => c.Value >= 2).Count() >= 1;

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

True

False

分析：

显而易见，BuddyStrings 的时间复杂度为： $O(n^{2})$ ，BuddyStrings2 的时间复杂度为： $O(n)$ 。

巴特西

C#LeetCode刷题之#859-亲密字符串（Buddy Strings）

最新文章

热门文章

巴特西

C#LeetCode刷题之#859-亲密字符串​​​​​​​​​​​​​​（Buddy Strings）

最新文章

热门文章

C#LeetCode刷题之#859-亲密字符串（Buddy Strings）