:-: 2.4 有效的字母异位词 ***** **题干：** 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。 示例 1: ``` 输入: s = "anagram", t = "nagaram" 输出: true ``` 示例 2: ``` 输入: s = "rat", t = "car" 输出: false ``` 示例 3: ``` 输入: s = "", t = "" 输出: true ``` 说明: ``` 你可以假设字符串只包含小写字母。 ``` 进阶: ``` 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？ ``` **题目分析：** 我们首先要验证两个字符串是否长度相同，长度都不同，就没有验证的必要了（），不要用equals方法判断两者（此方法也是由字符串转为byte数组，再一一验证数值是否相同，得不偿失），长度相同的情况下，再找出两者有区别的地方，如果以上验证大多都通过了说明两个字符组成相同。 **新手有可能遇到的解题思路陷阱：** 忽略了先觉条件长度必须一致，不一致就没有可比性了。 **解题思路分析以及代码实现：** 第一种思路：暴力破解。两层循环遍历两个字符串所化的数组，然后匹配，当匹配成功就OK,并赋值为字符‘A’,防止重复匹配。当有一个匹配不成功，就返回错误。此方法太过缓慢，只做参考。 **经过我的测试使用String的charAt()方法要比toCharArray()方法更加快捷一些，这里为什么使用了toCharArray()方法呢？？？因为String类型变量对比长度使用了length()方法，此方法也是字符串转为byte数组，返回数组长度，还不如使用toCharArray()方法，直接使用数组的长度。** 第一种思路代码： ``` public boolean isAnagram(String s, String t) { char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); if (ss.length != tt.length) return false; boolean sign = false; for (int i = 0; i < s.length(); i++) { sign = false; for (int j = 0; j < t.length(); j++) { if (ss[i] == tt[j]) { sign = true; tt[j] = 'A';// 以大写字母A替换小写字母，确保不会重复比对。 break; } } if (sign == false) { return sign; } } return sign; } ``` **复杂度分析** 时间复杂度：O(n^ 2)。 空间复杂度：O(n)。 第二种思路：集合法，如使用Map集合的<k,v>结构，首先必须满足两个字符串长度相等的条件，接着使用将字符串化为char类型的数组，将字符数组遍历加入Map集合，key是字符，value值是该字符出现的次数，接着将另一个字符数组的字符遍历，检查Map集合中是否有此字符，有就将该字符出现的次数减一，次数为零则删除此字符，无此字符就直接返回false。 或者使用List集合，首先必须满足长度相等的先决条件，然后将第一个字符串所有字符加入List集合，List集合减去第二个字符串中所有字符，再判断字符是否为空，不为空返回false，为空则true。 第二种思路代码1： ``` public boolean isAnagram(String s, String t) { char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); if (ss.length != tt.length) return false; Map<Character, Integer> map = new HashMap<Character, Integer>(); for (int i = 0; i < ss.length; i++) { char temp = ss[i]; if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } for (int i = 0; i < tt.length; i++) { char temp = tt[i]; if (!(map.containsKey(temp))) { return false; } else { map.put(temp, map.get(temp) - 1); if (map.get(temp) == 0) { map.remove(temp); } } } return true; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路2： ``` public boolean isAnagram(String s, String t) { char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); if (ss.length != tt.length) return false; List<Character> list = new ArrayList<Character>(); for (int i = 0; i < ss.length; i++) { list.add(ss[i]); } for (int i = 0; i < tt.length; i++) { list.remove((Character) tt[i]); } if (list.isEmpty()) { return true; } return false; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路：首先必须满足长度相等的先决条件，然后按字母顺序排序，在一一比对，不相同就返回错误。 Arrays.sort()方法也是有循环，但是里面是有多种排序方法，也可自行排序。 第三种思路代码： ``` public boolean isAnagram(String s, String t) { char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); if (ss.length != tt.length) return false; Arrays.sort(ss); Arrays.sort(tt); for (int i = 0; i < ss.length; i++) { if (ss[i] != tt[i]) { return false; } } return true; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第四种思路：数组法，首先字符拆串转化为字符数组，必须满足长度相等的先决条件，将字符与字符‘a’相减转int值，数值范围在[0,25]之间，一个加，一个减，如果能达到平衡，结果都为零，则代表互为异位词，反之不是。 第四种思路代码： ``` public boolean isAnagram(String s, String t) { char[] ss = s.toCharArray(); char[] tt = t.toCharArray(); if (ss.length != tt.length) return false; int[] letter = new int [26]; for (int i = 0; i < ss.length; i++) { letter[ss[i] - 'a']++; letter[tt[i] - 'a']--; } for (int i = 0; i < 26; i++) { if (letter[i] != 0) { return false; } } return true; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**