中国教育网站官网,东莞seo优化推广,网件路由器app,长春建站平台其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1操作 1 的本质#xff1a;字符可以任意排列
2.2操作 2 的本质#xff1a;出现次数是可以交换的
2.… 其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
2.1操作 1 的本质字符可以任意排列
2.2操作 2 的本质出现次数是可以交换的
2.3算法思路
三、代码
四、总结 前言
这是力扣的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 。
执行操作 1abc - acb
执行操作 1acb - bca示例 2 输入word1 a, word2 aa
输出false
解释不管执行多少次操作都无法从 word1 得到 word2 反之亦然。 示例 3 输入word1 cabbba, word2 abbccc
输出true
解释3 次操作从 word1 获得 word2 。
执行操作 1cabbba - caabbb
执行操作 2caabbb - baaccc
执行操作 2baaccc - 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 中有字符 abcword2 中有字符 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 的长度C26 是字符集大小。 空间复杂度O(C)。
