LC 1657. 确定两个字符串是否接近

题目描述

这是 LeetCode 上的 1657. 确定两个字符串是否接近 ，难度为 中等。

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

• 操作 1：交换任意两个 现有 字符。

  • 例如，abcde -> aecdb

• 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。

  • 例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a）

你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2。如果 word1 和 word2 接近 ，就返回 true；否则，返回 false。

示例 1：

输入：word1 = "abc", word2 = "bca"

输出：true

解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"

示例 2：

输入：word1 = "a", word2 = "aa"

输出：false

解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

示例 3：

输入：word1 = "cabbba", word2 = "abbccc"

输出：true

解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"

示例 4：

输入：word1 = "cabbba", word2 = "aabbss"

输出：false

解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

提示：

• $1 <= word1.length, word2.length <= 10^5$
• word1 和 word2 仅包含小写英文字母

---

模拟

两类操作都不会凭空产生或删除字符，而仅仅是对字符进行互换。

由于操作 1 和 2 都不限次数，因此我们只需检查「字符种类是否相同」和「字符频次是否相等」，即可得出两字符串是否接近的结论。

具体的，由于 s1 和 s2 都仅包含小写字母，因此可以创建两个大小为 26 的数组 c1 和 c2 分别对两字符串进行词频统计。

随后进行合法性检查：

1. 字符种类是否相同：若存在某个字符仅在 s1 或 s2 中出现过，两字符串必不接近，返回 False
2. 字符频次是否相等：对 c1 和 c2 进行排序，并逐项检查，若存在 c1[i] != c2[i]，说明存在词频为 c1[i] 的字符种类数在 s1 和 s2 间并不相等，返回 False

若上述两项检查无误，说明两字符串接近，返回 True。

Java 代码：

class Solution {
    public boolean closeStrings(String s1, String s2) {
        int[] c1 = new int[26], c2 = new int[26];
        for (char c : s1.toCharArray()) c1[c - 'a']++;
        for (char c : s2.toCharArray()) c2[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (c1[i] + c2[i] == 0) continue;
            if (c1[i] == 0 || c2[i] == 0) return false;
        }
        Arrays.sort(c1); Arrays.sort(c2);
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
}

Python 代码：

class Solution:
    def closeStrings(self, s1: str, s2: str) -> bool:
        c1, c2 = [0] * 26, [0] * 26
        for c in s1:
            c1[ord(c) - ord('a')] += 1
        for c in s2:
            c2[ord(c) - ord('a')] += 1
        for i in range(26):
            if c1[i] + c2[i] == 0:
                continue
            if c1[i] == 0 or c2[i] == 0:
                return False
        c1.sort()
        c2.sort()
        for i in range(26):
            if c1[i] != c2[i]:
                return False
        return True

C++ 代码：

class Solution {
public:
    bool closeStrings(string s1, string s2) {
        vector<int> c1(26, 0), c2(26, 0);
        for (char c : s1) c1[c - 'a']++;
        for (char c : s2) c2[c - 'a']++;
        for (int i = 0; i < 26; i++) {
            if (c1[i] + c2[i] == 0) continue;
            if (c1[i] == 0 || c2[i] == 0) return false;
        }
        sort(c1.begin(), c1.end());
        sort(c2.begin(), c2.end());
        for (int i = 0; i < 26; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }
};

TypeScirpt 代码：

function closeStrings(s1: string, s2: string): boolean {
    const c1: number[] = Array(26).fill(0);
    const c2: number[] = Array(26).fill(0);
    for (const c of s1) c1[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    for (const c of s2) c2[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    for (let i = 0; i < 26; i++) {
        if (c1[i] + c2[i] === 0) continue;
        if (c1[i] === 0 || c2[i] === 0) return false;
    }
    c1.sort((a, b) => a - b);
    c2.sort((a, b) => a - b);
    for (let i = 0; i < 26; i++) {
        if (c1[i] !== c2[i]) return false;
    }
    return true;
};

• 时间复杂度：统计词频复杂度为 $O(n + m)$；排序复杂度为 $O(C\log{C})$，其中 $C = 26$ 为字符集大小，进行合法性检查复杂度为 $O(C)$。整体复杂度为 $O(n + m + C\log{C})$
• 空间复杂度：$O(C)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1657 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。