前言
这是力扣的1657题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
一、题目描述
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
- 操作 1：交换任意两个 现有 字符。
- 例如，
abcde -> aecdb
- 例如，
- 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
- 例如，
aacabb -> bbcbaa（所有a转化为b，而所有的b转换为a）
- 例如，
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。
示例 1：
代码语言：javascript复制输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"示例 2：
代码语言：javascript复制输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。示例 3：
代码语言：javascript复制输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"示例 4：
代码语言：javascript复制输入：word1 = "cabbba", word2 = "aabbss"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。提示：
1 <= word1.length, word2.length <= 105word1和word2仅包含小写英文字母
二、题解
本题的关键就是看清楚两个操作的本质！
2.1操作 1 的本质：字符可以任意排列
我们可以随意洗牌。
例如示例1的word1 = "abc", word2 = "bca" (把一叠扑克洗成另一叠扑克）。
如果字符一样，但对应的出现次数不一样呢？这就需要用到操作 2 了。
2.2操作 2 的本质：出现次数是可以交换的
以示例 3 为例。统计 s = cabbba 的字符出现次数：
- a 出现 2 次。
- b 出现 3 次。
- c 出现 1 次。
我们可以把 a 都变成 b，同时把 b 都变成 a。
这相当于交换 a 和 b 的出现次数，得到：
- a 出现 3 次。
- b 出现 2 次。
- c 出现 1 次。
然后交换 a 和 c 的出现次数，得到：
- a 出现 1 次。
- b 出现 2 次。
- c 出现 3 次。
这便是字符串 t = abbccc 的字符出现次数。
所以「出现次数」是可以任意排列的。
2.3算法思路
- 判断 word1 和 word2 的长度是否一样，如果不一样直接返回 false。
- 判断 word1 和 word2 的字符集合是否一样，如果不一样直接返回 false。例如 word1 中有字符 abc，word2 中有字符 zxc，我们无论如何都不能把 word1 变成 word2 。
- 判断 word1 的字符出现次数的集合，是否等于 word2 的字符出现次数的集合，等于返回 true，不等于返回 false。注意集合可以有相同元素，比如 aabbbccc 对应的集合就是 {2,3,3}。
三、代码
代码语言：javascript复制class Solution {
public boolean closeStrings(String word1, String word2) {
if (word1.length() != word2.length()) {//判断长度
return false;
}
int[] count1 = new int[26], count2 = new int[26];
for (char c : word1.toCharArray()) {
count1[c - 97] ;
}
for (char c : word2.toCharArray()) {
count2[c - 97] ;
}
for (int i = 0; i < 26; i ) {//判断字符是否相等
if (count1[i] > 0 && count2[i] == 0 || count2[i] > 0 && count1[i] == 0) {
return false;
}
}
Arrays.sort(count1);
Arrays.sort(count2);
return Arrays.equals(count1, count2);//判断集合元素是否相等
}
}下面是简化版代码，但是上面的代码性能更好，如果两个字符串不相等，则直接不走下面的逻辑。
代码语言：javascript复制class Solution {
public boolean closeStrings(String word1, String word2) {
int[] count1 = new int[26], count2 = new int[26];
for (char c : word1.toCharArray()) {
count1[c - 97] ;
}
for (char c : word2.toCharArray()) {
count2[c - 97] ;
}
for (int i = 0; i < 26; i ) {
if (count1[i] > 0 && count2[i] == 0 || count2[i] > 0 && count1[i] == 0) {
return false;
}
}
Arrays.sort(count1);
Arrays.sort(count2);
return Arrays.equals(count1, count2);
}
}四、总结
复杂度分析：
- 时间复杂度：O(max{n1,n2} ClogC)，其中 n1 和 n2 分别是字符串 word1 和 word2 的长度，C=26 是字符集大小。
- 空间复杂度：O(C)。
