力扣---1657. 确定两个字符串是否接近

allWu / 2023-05-03 / 原文

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

操作 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 <= 105
word1 和 word2 仅包含小写英文字母

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/determine-if-two-strings-are-close
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

可以想到，两个字符串符合题意时，有两个特点：

1. 两个字符串中所有字符的种类相同。

2. 两个字符串中各字符总数的次数相同。（比如 aa 中 a 的字符总数是 2 ，bb 中 b 的字符总数是 2，即 aa 和 bb 视为符合第二个要求。）

可以想到利用哈希表来存储两者的所有字符以及频率，先判断第一个特点，然后判断第二个特点。

class Solution {
    public boolean closeStrings(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 长度不等，必定不接近
        if (len1 != len2) {
            return false;
        }
        Map<Character, Integer> map1 = new HashMap<>();
        // 将 word1 中的所有字符和出现次数存入 map1。
        for (int i = 0; i < len1; i ++) {
            char tem = word1.charAt(i);
            map1.put(tem, map1.getOrDefault(tem, 0) + 1);
        }
        Map<Character, Integer> map2 = new HashMap<>();
        for (int i = 0; i < len1; i ++) {
            char tem = word2.charAt(i);
            // 判断第一个特点，即两者字符串的种类相同。
            if (!map1.containsKey(tem)) {
                return false;
            }
            map2.put(tem, map2.getOrDefault(tem, 0) + 1);
        }
        // 开始判断第二个特点。
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer x : map1.values()) {
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        for (Integer x : map2.values()) {
            if (map.containsKey(x)) {
                int tem = map.get(x);
                if (tem > 1) {
                    map.put(x, tem - 1);
                } else {
                    map.remove(x);
                }
            } else {
                return false;
            }
        }
        return map.size() == 0;
    }
}