1.有效的字母异位词（242-易）
题目描述：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词（字母相同位置不同）。进阶问题的核心点在于「字符是离散未知的」
示例：
输入: s = "anagram", t = "nagaram" 输出: true 输入: s = "rat", t = "car" 输出: false
思路：本题核心是记录出现字母的次数（数组或者hashmap），当两个字符串出现字母类别相同且数量相等，则为异位词。有两种思路：
- hashmap键值对进行记录是比较经典的方法。
- 也可以直接用数组记录字符出现的次数。
代码实现：
class Solution { // hashmap public boolean isAnagram1(String s, String t) { if (s.length() != t.length()) { return false; } HashMap<Character, Integer> map = new HashMap<>(); for (char cs : s.toCharArray()) { map.put(cs, map.getOrDefault(cs, 0) + 1); } for (char ct : t.toCharArray()) { map.put(ct, map.getOrDefault(ct, 0) - 1); if (map.get(ct) == -1) { return false; } } return true; } // 数组计数(推荐) public boolean isAnagram(String s, String t) { if (s.length() != t.length()) { return false; } // 记录字母出现的次数 int[] counts = new int[26]; for (char cs : s.toCharArray()) { counts[cs - 'a']++; } for (char ct : t.toCharArray()) { counts[ct - 'a']--; } for (int num : counts) { if (num != 0) { return false; } } return true; } }
ps：这个比较耗时，hashmap初始容量16，感觉扩容耗时！！
拓展：字母的异位词分组（T49）
思路：如何知道两个单词是异位词？排序或者计数！
- 排序：将排序后的字符串作为键（先转成字符数组，根据ascii码进行排序）
- 计数：自定义编码作为键
注意：map的key必须是String类型！不能是字符数组，原因是String重写了HashCode()和equalls()map.values()获取map的所有值。
代码实现：
class Solution { // 排序法(对每个字母进行重排序) public List<List<String>> groupAnagrams(String[] strs) { Map<String, ArrayList<String>> map = new HashMap<>(); for (String str : strs) { char[] chs = str.toCharArray(); Arrays.sort(chs); // 特别注意：要将字符数组转化为字符串，因为String实现了equals和hashCode方法 String key = String.valueOf(chs); if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(str); } return new ArrayList(map.values()); } // 计数法（两个数互为异位词：字母出现的次数相同） public List<List<String>> groupAnagrams(String[] strs) { Map<String, ArrayList<String>> map = new HashMap<>(); for (String str : strs) { char[] chs = str.toCharArray(); int[] counts = new int[26]; for (char c : chs) { counts[c - 'a']++; } // 将字符数组编码为字符串，比如将 [b,a,a,a,b,c] 编码成 a3b2c1 StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++) { if (counts[i] != 0) { sb.append((char)('a' + i)); sb.append(counts[i]); } } String key = sb.toString(); if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(str); } return new ArrayList(map.values()); } }
6.同构字符串（205-易）
题目描述：如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序！。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例：
输入：s = "egg", t = "add" 输出：true 输入：s = "foo", t = "bar" 输出：false
思路：本题映射的关键是每个字符只能映射到一个字符（单映射，即s通过映射可以得到t），且映射位置不能错。解决方案：
- 常规解法：建立两个hashmap进行映射，如示例中，t 中的字符 a 和 r 虽然有唯一的映射 o，但对于 s 中的字符 o来说其存在两个映射 {a,r}，故不满足条件。但这种方法效率比较低。
- 记录一个字符串上次出现的位置，如果两个字符串中字符上次出现的位置不一致，一定不是同构；否则，更新该字符上次出现的位置。
代码：
public boolean isIsomorphic(String s, String t) { Map<Character, Character> s2t = new HashMap<Character, Character>(); Map<Character, Character> t2s = new HashMap<Character, Character>(); int len = s.length(); for (int i = 0; i < len; ++i) { char x = s.charAt(i), y = t.charAt(i); if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) { return false; } s2t.put(x, y); t2s.put(y, x); } return true; } public boolean isIsomorphic(String s, String t) { // 记录两个字符串每个字符上一次出现的位置（一共256个字符） int[] preIndexOfS = new int[256]; int[] preIndexOfT = new int[256]; for (int i = 0; i < s.length(); i++) { char sc = s.charAt(i), tc = t.charAt(i); if (preIndexOfS[sc] != preIndexOfT[tc]) { return false; } // 字符相同，更新位置 preIndexOfS[sc] = i + 1; preIndexOfT[tc] = i + 1; } return true; }
7.单词规律（290-易）
题目描述：给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。
这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
示例：
输入: pattern = "abba", str = "dog cat cat dog" 输出: true
思路：基本思路与上题相同，创建两个hash表，建立双向映射（字符串和字符之间的映射）。注意：字符串的比较用equals，String对equals进行了重写，实际是比较的内容！
代码：
public boolean wordPattern(String pattern, String s) { HashMap<Character, String> map1 = new HashMap<>(); HashMap<String, Character> map2 = new HashMap<>(); String[] ss = s.split(" "); if (pattern.length() != ss.length) { return false; } int i = 0; for (char ch : pattern.toCharArray()) { if (map1.containsKey(ch) && !map1.get(ch).equals(ss[i]) || map2.containsKey(ss[i]) && !map2.get(ss[i]).equals(ch)) { return false; } map1.put(ch, ss[i]); map2.put(ss[i], ch); i++; } return true; }
