其他系列文章导航
文章目录
前言
这是力扣的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 <= 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}。
三、代码
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);//判断集合元素是否相等 } }
下面是简化版代码，但是上面的代码性能更好，如果两个字符串不相等，则直接不走下面的逻辑。
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)。
