字母异位词分组https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-100-liked哈希表字母异位词分组https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-100-liked哈希表存储每一组字母异位词哈希表的键为一组字母异位词的标志哈希表的值为一组字母异位词列表遍历每个字符串对于每个字符串得到该字符串所在的一组字母异位词的标志将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后哈希表中的每个键值对即为一组字母异位词。一·排序 哈希表的方法解题思路核心思想两个字符串互为字母异位词Anagram当且仅当它们包含的字母及其数量完全相同只是排列顺序不同。因此如果将两个互为字母异位词的字符串分别进行排序得到的结果一定是相同的字符串。具体步骤初始化哈希表创建一个MapString, ListString用于存储分组结果。键 (Key)排序后的字符串作为该组字母异位词的唯一标识。值 (Value)原始字符串组成的列表。遍历输入数组对于输入的字符串数组strs中的每一个字符串str将字符串转换为字符数组。对字符数组进行排序Arrays.sort。将排序后的字符数组重新转换为字符串作为哈希表的key。检查哈希表中是否存在该key如果存在获取对应的列表将原始字符串str加入列表。如果不存在创建一个新的列表将str加入并将key, list存入哈希表。返回结果遍历结束后哈希表中所有的value即各个列表组合起来就是最终结果。1public ListListString groupAnagrams(String[] strs) { 2 // 1. 创建哈希表key是排序后的字符串value是原始字符串的列表 3 MapString, ListString map new HashMapString, ListString(); 4 5 // 2. 遍历每个字符串 6 for (String str : strs) { 7 // 将字符串转为字符数组以便排序 8 char[] array str.toCharArray(); 9 // 对字符数组排序例如 eat - [a, e, t] 10 Arrays.sort(array); 11 // 将排序后的数组转回字符串作为 key例如 aet 12 String key new String(array); 13 14 // 3. 获取或创建列表 15 // 如果 map 中已有 key则返回对应的列表否则创建一个新的 ArrayList 16 ListString list map.getOrDefault(key, new ArrayListString()); 17 18 // 将原始字符串加入列表 19 list.add(str); 20 21 // 将更新后的列表放回 map如果是新创建的列表这步是存入如果是已有的这步是更新引用虽然后者非必须但逻辑清晰 22 map.put(key, list); 23 } 24 25 // 4. 返回 map 中所有 value 组成的列表 26 return new ArrayListListString(map.values()); 27}复杂度分析时间复杂度 O(N⋅KlogK)O(N⋅KlogK)NN 是字符串数组strs的长度。KK 是字符串的最大长度。我们需要遍历 NN 个字符串对于每个字符串排序需要 O(KlogK)O(KlogK) 的时间构建 key 和更新哈希表需要 O(K)O(K) 或 O(1)O(1) 的时间。主导因素是排序。空间复杂度 O(N⋅K)O(N⋅K)需要用哈希表存储所有的字符串内容。在最坏情况下所有字符串都不互为字母异位词或者都互为字母异位词都需要存储所有字符。二·计数 哈希表。这种方法的核心区别在于如何生成哈希表的键Key。核心思路字符计数法原理两个字符串互为字母异位词当且仅当它们包含的每个字母a 到 z的出现次数完全相同。构建 Key创建一个长度为 26 的整型数组代码中用了char[]效果类似用来统计当前字符串中每个字母出现的次数。索引0代表 a 的次数索引1代表 b 的次数以此类推。将这个统计数组直接转换为字符串new String(num)作为哈希表的Key。因为字母顺序是固定的从 a 到 z所以只要两个字符串的字母频次相同生成的这个字符串 Key 就必然相同。分组逻辑如果 Map 中已经存在这个 Key说明之前遇到过同组的异位词直接将当前字符串加入对应的列表。如果不存在创建新列表加入当前字符串放入 Map同时也加入结果集res。1public ListListString groupAnagrams(String[] strs) { 2 // 哈希表Key 是“频次特征字符串”Value 是该组的所有原始字符串 3 HashMapString, ListString map new HashMap(); 4 // 最终结果列表 5 ListListString res new ArrayList(); 6 7 for (String str : strs) { 8 // 1. 初始化计数数组长度26对应26个小写字母 9 // 注意这里用 char[] 是为了方便最后直接 new String()虽然存的是次数int但隐式转换没问题 10 char[] num new char[26]; 11 char[] charArray str.toCharArray(); 12 13 // 2. 统计每个字符出现的次数 14 for (char c : charArray) { 15 num[c - a]; // a-0, b-1, ... 16 } 17 18 // 3. 将计数数组转换为字符串作为 Key 19 // 例如aab - [2, 1, 0, ..., 0] - 字符串 \u0002\u0001... 20 String sb new String(num); 21 22 // 4. 根据 Key 进行分组 23 if (map.containsKey(sb)) { 24 // 如果组已存在直接添加 25 map.get(sb).add(str); 26 } else { 27 // 如果组不存在创建新组 28 ArrayListString stringArrayList new ArrayList(); 29 stringArrayList.add(str); 30 map.put(sb, stringArrayList); 31 // 关键点直接将新创建的列表引用加入结果集 res 32 // 这样后续通过 map.get(sb) 修改列表时res 中的列表也会同步更新 33 res.add(stringArrayList); 34 } 35 } 36 return res; 37}与“排序法”的对比表格特性排序法计数法Key 生成方式对字符串字符排序 (e.g., eat - aet)统计字母频次转字符串 (e.g., eat - [1,0,...,1,0...,1...] - String)时间复杂度O(N⋅KlogK)O(N⋅KlogK)( KK 是字符串长度主要耗时在排序)O(N⋅K)O(N⋅K)(只需遍历一次字符串统计频次无需排序)空间复杂度O(N⋅K)O(N⋅K)O(N⋅K)O(N⋅K)(Key 的长度固定为 26但在 Java 中new String(char[])会占用空间)适用场景通用字符集不限或很大时也可用需调整排序逻辑特别适合字符集较小且固定的情况如仅限小写英文字母性能表现较慢受限于排序算法更快线性时间复杂度潜在的小细节与优化char[]用于计数代码中使用char[] num来存储计数。虽然通常计数用int[]但这里为了利用new String(char[])构造函数直接生成 Key使用了char[]。风险如果某个字母出现次数超过Character.MAX_VALUE(65535)会发生溢出。但在一般的字母异位词题目中字符串长度通常远小于这个值所以是安全的。Key 的可读性生成的 Key 包含很多不可见字符ASCII 码小于 32 的控制字符。例如如果 a 出现 2 次b 出现 1 次Key 的前两个字符就是 ASCII 值为 2 和 1 的字符。这在调试时可能不太直观但在逻辑上是完全正确的因为 Java 的 String 区分这些字符。替代方案有些实现会将计数数组拼接成#2#1#0...这样的可读字符串作为 Key虽然稍微慢一点字符串拼接开销但调试更友好。不过当前的new String(num)方式在性能上是最优的。方案二优化class Solution { public ListListString groupAnagrams(String[] strs) { if (strs null ||strs.length0){ return new ArrayList(); } MapString,ListString map new HashMap(); for(String str :strs) { char[] num new char[26]; char[] charArray str.toCharArray(); for(char c : charArray){ num[c- a]; } String sb new String(num); map.computeIfAbsent(sb,k - new ArrayList()).add(str); } return new ArrayList(map.values()); } }computeIfAbsent是 Java 8 引入的Map接口中的一个默认方法它极大地简化了“如果键不存在则创建新值否则获取现有值”这种常见逻辑。来源力扣LeetCode
LeetCode 49. 字母异位词分组
发布时间：2026/5/19 23:41:17
字母异位词分组https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-100-liked哈希表字母异位词分组https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-100-liked哈希表存储每一组字母异位词哈希表的键为一组字母异位词的标志哈希表的值为一组字母异位词列表遍历每个字符串对于每个字符串得到该字符串所在的一组字母异位词的标志将当前字符串加入该组字母异位词的列表中。遍历全部字符串之后哈希表中的每个键值对即为一组字母异位词。一·排序 哈希表的方法解题思路核心思想两个字符串互为字母异位词Anagram当且仅当它们包含的字母及其数量完全相同只是排列顺序不同。因此如果将两个互为字母异位词的字符串分别进行排序得到的结果一定是相同的字符串。具体步骤初始化哈希表创建一个MapString, ListString用于存储分组结果。键 (Key)排序后的字符串作为该组字母异位词的唯一标识。值 (Value)原始字符串组成的列表。遍历输入数组对于输入的字符串数组strs中的每一个字符串str将字符串转换为字符数组。对字符数组进行排序Arrays.sort。将排序后的字符数组重新转换为字符串作为哈希表的key。检查哈希表中是否存在该key如果存在获取对应的列表将原始字符串str加入列表。如果不存在创建一个新的列表将str加入并将key, list存入哈希表。返回结果遍历结束后哈希表中所有的value即各个列表组合起来就是最终结果。1public ListListString groupAnagrams(String[] strs) { 2 // 1. 创建哈希表key是排序后的字符串value是原始字符串的列表 3 MapString, ListString map new HashMapString, ListString(); 4 5 // 2. 遍历每个字符串 6 for (String str : strs) { 7 // 将字符串转为字符数组以便排序 8 char[] array str.toCharArray(); 9 // 对字符数组排序例如 eat - [a, e, t] 10 Arrays.sort(array); 11 // 将排序后的数组转回字符串作为 key例如 aet 12 String key new String(array); 13 14 // 3. 获取或创建列表 15 // 如果 map 中已有 key则返回对应的列表否则创建一个新的 ArrayList 16 ListString list map.getOrDefault(key, new ArrayListString()); 17 18 // 将原始字符串加入列表 19 list.add(str); 20 21 // 将更新后的列表放回 map如果是新创建的列表这步是存入如果是已有的这步是更新引用虽然后者非必须但逻辑清晰 22 map.put(key, list); 23 } 24 25 // 4. 返回 map 中所有 value 组成的列表 26 return new ArrayListListString(map.values()); 27}复杂度分析时间复杂度 O(N⋅KlogK)O(N⋅KlogK)NN 是字符串数组strs的长度。KK 是字符串的最大长度。我们需要遍历 NN 个字符串对于每个字符串排序需要 O(KlogK)O(KlogK) 的时间构建 key 和更新哈希表需要 O(K)O(K) 或 O(1)O(1) 的时间。主导因素是排序。空间复杂度 O(N⋅K)O(N⋅K)需要用哈希表存储所有的字符串内容。在最坏情况下所有字符串都不互为字母异位词或者都互为字母异位词都需要存储所有字符。二·计数 哈希表。这种方法的核心区别在于如何生成哈希表的键Key。核心思路字符计数法原理两个字符串互为字母异位词当且仅当它们包含的每个字母a 到 z的出现次数完全相同。构建 Key创建一个长度为 26 的整型数组代码中用了char[]效果类似用来统计当前字符串中每个字母出现的次数。索引0代表 a 的次数索引1代表 b 的次数以此类推。将这个统计数组直接转换为字符串new String(num)作为哈希表的Key。因为字母顺序是固定的从 a 到 z所以只要两个字符串的字母频次相同生成的这个字符串 Key 就必然相同。分组逻辑如果 Map 中已经存在这个 Key说明之前遇到过同组的异位词直接将当前字符串加入对应的列表。如果不存在创建新列表加入当前字符串放入 Map同时也加入结果集res。1public ListListString groupAnagrams(String[] strs) { 2 // 哈希表Key 是“频次特征字符串”Value 是该组的所有原始字符串 3 HashMapString, ListString map new HashMap(); 4 // 最终结果列表 5 ListListString res new ArrayList(); 6 7 for (String str : strs) { 8 // 1. 初始化计数数组长度26对应26个小写字母 9 // 注意这里用 char[] 是为了方便最后直接 new String()虽然存的是次数int但隐式转换没问题 10 char[] num new char[26]; 11 char[] charArray str.toCharArray(); 12 13 // 2. 统计每个字符出现的次数 14 for (char c : charArray) { 15 num[c - a]; // a-0, b-1, ... 16 } 17 18 // 3. 将计数数组转换为字符串作为 Key 19 // 例如aab - [2, 1, 0, ..., 0] - 字符串 \u0002\u0001... 20 String sb new String(num); 21 22 // 4. 根据 Key 进行分组 23 if (map.containsKey(sb)) { 24 // 如果组已存在直接添加 25 map.get(sb).add(str); 26 } else { 27 // 如果组不存在创建新组 28 ArrayListString stringArrayList new ArrayList(); 29 stringArrayList.add(str); 30 map.put(sb, stringArrayList); 31 // 关键点直接将新创建的列表引用加入结果集 res 32 // 这样后续通过 map.get(sb) 修改列表时res 中的列表也会同步更新 33 res.add(stringArrayList); 34 } 35 } 36 return res; 37}与“排序法”的对比表格特性排序法计数法Key 生成方式对字符串字符排序 (e.g., eat - aet)统计字母频次转字符串 (e.g., eat - [1,0,...,1,0...,1...] - String)时间复杂度O(N⋅KlogK)O(N⋅KlogK)( KK 是字符串长度主要耗时在排序)O(N⋅K)O(N⋅K)(只需遍历一次字符串统计频次无需排序)空间复杂度O(N⋅K)O(N⋅K)O(N⋅K)O(N⋅K)(Key 的长度固定为 26但在 Java 中new String(char[])会占用空间)适用场景通用字符集不限或很大时也可用需调整排序逻辑特别适合字符集较小且固定的情况如仅限小写英文字母性能表现较慢受限于排序算法更快线性时间复杂度潜在的小细节与优化char[]用于计数代码中使用char[] num来存储计数。虽然通常计数用int[]但这里为了利用new String(char[])构造函数直接生成 Key使用了char[]。风险如果某个字母出现次数超过Character.MAX_VALUE(65535)会发生溢出。但在一般的字母异位词题目中字符串长度通常远小于这个值所以是安全的。Key 的可读性生成的 Key 包含很多不可见字符ASCII 码小于 32 的控制字符。例如如果 a 出现 2 次b 出现 1 次Key 的前两个字符就是 ASCII 值为 2 和 1 的字符。这在调试时可能不太直观但在逻辑上是完全正确的因为 Java 的 String 区分这些字符。替代方案有些实现会将计数数组拼接成#2#1#0...这样的可读字符串作为 Key虽然稍微慢一点字符串拼接开销但调试更友好。不过当前的new String(num)方式在性能上是最优的。方案二优化class Solution { public ListListString groupAnagrams(String[] strs) { if (strs null ||strs.length0){ return new ArrayList(); } MapString,ListString map new HashMap(); for(String str :strs) { char[] num new char[26]; char[] charArray str.toCharArray(); for(char c : charArray){ num[c- a]; } String sb new String(num); map.computeIfAbsent(sb,k - new ArrayList()).add(str); } return new ArrayList(map.values()); } }computeIfAbsent是 Java 8 引入的Map接口中的一个默认方法它极大地简化了“如果键不存在则创建新值否则获取现有值”这种常见逻辑。来源力扣LeetCode
