确定两个字符串是否接近

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

操作 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 仅包含小写英文字母

哈希表计数

• 因为只含有小写字母只需要用26个字母的哈希表

根据题意，两个字符要接近必须满足三个条件

• 两个字符串的长度一定相同
• 两个字符串的字符的种类一定相同
• 两个字符串的对应字符的数量不一定相同，但是在另一个字符串中一定有数量相同但种类不同的字符，不然无法通过替换生成相同的。

class Solution {
    public boolean closeStrings(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        if (m != n) return false;

        int[] hash1 = new int[26];
        int[] hash2 = new int[26];

        for (int i = 0; i < m; i++) {
            hash1[word1.charAt(i) - 'a']++;
            hash2[word2.charAt(i) - 'a']++;
        }
        // 要相似，含有的字符的种类相同
        for (int i = 0; i < 26; i++) {
            // 进行种类对应
            if ((hash1[i] > 0 && hash2[i] == 0) || (hash2[i] > 0 && hash1[i] == 0)) return false;
        }
        
        // 两个字符串的对应字符的数量不一定相同，
        // 但是在另一个字符串中一定有数量相同但种类不同的字符，
        // 不然无法通过替换生成相同的。
        Arrays.sort(hash1);
        Arrays.sort(hash2);

        // 进行数量对应
        for (int i = 0; i < 26; i++) {
            if (hash1[i] != hash2[i]) return false;
        }
        return true;
    }
}

时间复杂度$O(n)$ 空间复杂度$O(1)$

赏

谢谢你请我吃糖果

微信