在力扣LeetCode刷题时你是否遇到过这样的场景题目要求将一组字符串按照“字母异位词”进行分组乍一看思路清晰但动手实现时却总在哈希表的键设计、排序效率或边界条件上卡壳网上题解虽多但往往只给最优解对于“为什么要这么做”、“还有哪些坑”却语焉不详导致自己下次遇到类似问题依然无从下手。本文将以力扣第49题「字母异位词分组」为蓝本为你彻底拆解这道经典哈希表应用题。我们将从最朴素的暴力思路开始一步步推导到最优解不仅给出可直接复制运行的多种语言代码更会深入探讨哈希表的核心思想、字符串排序的代价以及不同数据规模下的策略选择。无论你是正在准备面试的应届生还是希望巩固算法基础的在职开发者这篇教程都能让你真正理解其精髓做到举一反三。1. 问题背景与核心概念拆解在深入代码之前我们必须先厘清几个关键概念这是理解所有后续解决方案的基础。1.1 什么是字母异位词字母异位词英文称 “Anagram”是指由相同字母、通过重新排列顺序而构成的不同单词或短语。例如eat、tea、ate就是一组字母异位词。它们都包含字母a,e,t只是顺序不同。bat和tab是另一组。hello和olelh也是一组。而eat和car则不是因为字母组成完全不同。判断两个字符串是否为字母异位词的核心标准是忽略顺序后它们包含的字符及其出现次数是否完全相同。1.2 力扣第49题字母异位词分组题目描述给你一个字符串数组strs请你将字母异位词组合在一起。可以按任意顺序返回结果列表。示例 1输入strs [eat, tea, tan, ate, nat, bat] 输出[[bat],[nat,tan],[ate,eat,tea]]示例 2输入strs [] 输出[[]]示例 3输入strs [a] 输出[[a]]题目解读输入一个字符串数组可能包含空字符串。任务将数组中所有互为字母异位词的字符串分到同一个子列表中。输出一个列表的列表每个子列表包含一组字母异位词。子列表之间的顺序、子列表内字符串的顺序均无要求。核心挑战如何高效地判断两个字符串是否为字母异位词并将它们关联起来。1.3 为什么这道题重要这道题是力扣上的经典题目其重要性体现在多个层面面试高频它综合考察了对哈希表的灵活运用、字符串处理能力以及对排序算法的理解是检验候选人基础数据结构掌握程度的绝佳题目。算法思想它完美体现了“键-值”映射和“归一化”的思想。将复杂、多变的数据字符串转化为一个统一的、可比较的“键”是解决许多分类、聚合问题的通用模式。性能优化从暴力法到优化解法的演进过程是学习算法时间复杂度和空间复杂度分析的生动案例。2. 环境准备与思路演进在开始编码前我们不需要特定的IDE或复杂的项目结构。任何支持你所用编程语言的环境即可。本文将提供Python和Java两种主流语言的实现你可以选择自己熟悉的语言跟随练习。核心思路演进路线图我们将按照由浅入深、从低效到高效的顺序探讨三种主要解法暴力法理解问题本质双重循环逐个比较。排序哈希表法最直观的优化将排序后的字符串作为哈希表的键。计数哈希表法更优的优化将字符计数数组转换为字符串作为键。理解每一种方法的优缺点比单纯记住最优解代码更重要。3. 解法一暴力比较法理解基础这是最直接的想法遍历每个字符串对于当前字符串再遍历结果列表检查它是否与某个已有分组中的第一个字符串是字母异位词。如果是则加入该组否则以它为首创建一个新组。关键问题如何判断两个字符串是字母异位词暴力法下的判断通常有两种排序比较将两个字符串分别排序如果排序后相等则是异位词。计数比较统计两个字符串中每个字符的出现次数如果计数数组完全相同则是异位词。这里我们先用排序比较来实现暴力法以便后续对比。Python 实现class Solution: def groupAnagrams(self, strs): :type strs: List[str] :rtype: List[List[str]] groups [] # 用于存储最终分组的列表 used [False] * len(strs) # 标记字符串是否已被分组 for i in range(len(strs)): if used[i]: continue # 如果当前字符串已处理过跳过 current_group [strs[i]] # 以当前字符串创建一个新组 used[i] True # 拿当前字符串去和后面所有未使用的字符串比较 for j in range(i 1, len(strs)): if used[j]: continue # 判断 strs[i] 和 strs[j] 是否为字母异位词通过排序 if sorted(strs[i]) sorted(strs[j]): current_group.append(strs[j]) used[j] True # 标记为已使用 groups.append(current_group) # 将当前组加入结果 return groups # 测试代码 if __name__ __main__: sol Solution() test_cases [ [eat, tea, tan, ate, nat, bat], [], [a] ] for strs in test_cases: print(f输入: {strs}) print(f输出: {sol.groupAnagrams(strs)}) print(- * 30)Java 实现import java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { ListListString groups new ArrayList(); boolean[] used new boolean[strs.length]; for (int i 0; i strs.length; i) { if (used[i]) { continue; } ListString currentGroup new ArrayList(); currentGroup.add(strs[i]); used[i] true; char[] baseChars strs[i].toCharArray(); Arrays.sort(baseChars); String baseSorted new String(baseChars); for (int j i 1; j strs.length; j) { if (used[j]) { continue; } char[] compareChars strs[j].toCharArray(); Arrays.sort(compareChars); String compareSorted new String(compareChars); if (baseSorted.equals(compareSorted)) { currentGroup.add(strs[j]); used[j] true; } } groups.add(currentGroup); } return groups; } // 测试代码 public static void main(String[] args) { Solution sol new Solution(); String[][] testCases { {eat, tea, tan, ate, nat, bat}, {}, {a} }; for (String[] strs : testCases) { System.out.println(输入: Arrays.toString(strs)); System.out.println(输出: sol.groupAnagrams(strs)); System.out.println(------------------------------); } } }复杂度分析与缺陷时间复杂度O(n² * k log k)其中 n 是字符串数组的长度k 是单个字符串的最大长度。外层循环 O(n)内层循环最坏 O(n)每次比较需要排序 O(k log k)。当 n 很大时效率极低。空间复杂度O(n)用于存储结果和标记数组。主要缺陷进行了大量重复的排序操作。例如tea和ate都与eat比较了一次tea和ate之间可能还会再比较一次每次都重新排序。这个解法帮助我们理解了问题的核心——分组但其性能无法接受。接下来我们需要一个更聪明的方法来避免重复比较。4. 解法二排序哈希表法标准解法这是本题最经典、最直观的优化解法。其核心思想是既然字母异位词排序后相同那么排序后的字符串就可以作为它们的“唯一标识”或“键”。算法步骤创建一个哈希表字典/Map键Key是排序后的字符串值Value是一个列表用于存放所有能排序成该键的原字符串。遍历输入的字符串数组。对每个字符串先将其转换为字符数组并排序得到排序后的字符串作为key。在哈希表中查找这个key如果存在则将当前原字符串添加到该key对应的值列表中。如果不存在则以当前key创建一个新列表并将原字符串放入然后将这个键值对存入哈希表。遍历结束后哈希表中所有的值即那些列表就是最终的分组结果。这个方法的妙处在于每个字符串只需要排序一次然后通过哈希表 O(1) 的时间复杂度完成查找和归类。Python 实现class Solution: def groupAnagrams(self, strs): :type strs: List[str] :rtype: List[List[str]] from collections import defaultdict # 使用 defaultdict(list)当key不存在时自动创建一个空列表作为value anagram_map defaultdict(list) for s in strs: # 将字符串排序得到唯一的键 # sorted(s) 返回列表需要 join 成字符串 key .join(sorted(s)) # 将原字符串 s 加入到对应 key 的列表中 anagram_map[key].append(s) # 返回哈希表中所有值的列表 return list(anagram_map.values()) # 更简洁的写法理解后可以使用 class SolutionConcise: def groupAnagrams(self, strs): anagram_map {} for s in strs: key tuple(sorted(s)) # 使用元组作为key也是常见的做法 anagram_map[key] anagram_map.get(key, []) [s] return list(anagram_map.values())Java 实现import java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { // Key: 排序后的字符串 Value: 对应的原字符串列表 MapString, ListString map new HashMap(); for (String s : strs) { // 将字符串转换为字符数组并排序 char[] charArray s.toCharArray(); Arrays.sort(charArray); String key new String(charArray); // 排序后的字符串作为key // 如果map中不存在这个key就创建一个新的列表 // 等价于 map.computeIfAbsent(key, k - new ArrayList()).add(s); if (!map.containsKey(key)) { map.put(key, new ArrayList()); } // 将原字符串添加到对应的列表中 map.get(key).add(s); } // 直接返回map中所有value构成的集合 return new ArrayList(map.values()); } } // 使用Java 8 Stream API的简洁写法 class SolutionStream { public ListListString groupAnagrams(String[] strs) { return new ArrayList(Arrays.stream(strs) .collect(Collectors.groupingBy(s - { char[] chars s.toCharArray(); Arrays.sort(chars); return new String(chars); })).values()); } }复杂度分析时间复杂度O(n * k log k)。遍历 n 个字符串是 O(n)对每个长度为 k 的字符串排序是 O(k log k)。这是主要的性能开销。空间复杂度O(n * k)。哈希表需要存储所有字符串。最坏情况下没有异位词每个键值对存储一个字符串键是排序后的字符串长度k值列表里有一个原字符串长度k。这是面试中最常被接受的答案。它清晰、高效并且易于理解和实现。5. 解法三计数哈希表法另一种优化思路当字符串只包含小写字母时这是一个常见的约束或假设我们可以使用一个更高效的方法来生成“键”从而避免排序的 O(k log k) 开销。核心思想用一个长度为26的数组对应26个小写字母统计每个字符串中字符出现的次数。然后把这个计数数组转换成一个格式固定的字符串例如#1#2#0...#1作为哈希表的键。例如abbccc的计数数组是[1, 2, 3, 0, 0, ...]可以表示为键“#1#2#3#0#0...”。任何字母异位词都会有完全相同的计数数组因此也会有相同的键。算法步骤创建一个哈希表。遍历每个字符串。对于每个字符串初始化一个长度为26、值全为0的计数数组count。遍历字符串的每个字符c执行count[c - a]。将计数数组转换为一个唯一的字符串键。通常使用分隔符如#连接每个计数以防止歧义例如[11, 0]和[1, 10]直接拼接成字符串会混淆。以该键在哈希表中进行查找和分组同解法二。Python 实现class Solution: def groupAnagrams(self, strs): from collections import defaultdict anagram_map defaultdict(list) for s in strs: # 初始化一个26个0的列表对应a-z count [0] * 26 for char in s: # 计算字符在字母表中的索引并增加计数 count[ord(char) - ord(a)] 1 # 将计数列表转换为一个元组作为哈希表的键 # 元组是可哈希的列表不行 key tuple(count) anagram_map[key].append(s) return list(anagram_map.values())Java 实现class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } // 将计数数组转换为一个特征字符串 // 使用 StringBuilder 和分隔符 ‘#’ 来构建键避免歧义 StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#); sb.append(count[i]); } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }复杂度分析时间复杂度O(n * k)。遍历 n 个字符串是 O(n)对每个字符串统计字符次数是 O(k)构建键字符串是 O(26) 即 O(1)。因此总体是 O(n * k)。空间复杂度O(n * k)。哈希表存储所有字符串此外每个键是一个长度为固定如 26*数字位数分隔符长度的字符串。对比与选择当 k字符串平均长度较小或者 k log k 与 k 相差不大时两种方法性能接近。排序法代码更简洁。当 k 非常大例如字符串很长时计数法 O(n * k) 理论上优于排序法 O(n * k log k)。当字符串可能包含非小写字母如大写、数字、空格时排序法是通用解法。计数法需要根据字符集大小调整数组长度。在面试中通常可以先提出排序法然后面试官可能会追问“如果字符串很长怎么办”此时再引出计数法展示你思维的层次和优化能力。6. 完整测试与运行验证为了确保代码的正确性我们需要设计全面的测试用例。一个好的测试集应该包括普通用例多个分组。边界用例空数组、包含空字符串的数组、只有一个字符串的数组。特殊用例所有字符串都是异位词、所有字符串都互不是异位词。长字符串用例测试性能。下面是一个综合的测试示例以Python为例def test_group_anagrams(): solution Solution() # 使用上面任一解法类 test_cases [ { input: [eat, tea, tan, ate, nat, bat], expected_sets: [{bat}, {nat, tan}, {ate, eat, tea}] # 使用集合比较忽略顺序 }, { input: [], expected_sets: [{}] }, { input: [a], expected_sets: [{a}] }, { input: [, ], expected_sets: [{, }] # 两个空字符串应为一组 }, { input: [abc, bca, cab, acb], # 全为异位词 expected_sets: [{abc, bca, cab, acb}] }, { input: [abc, def, ghi], # 全不为异位词 expected_sets: [{abc}, {def}, {ghi}] }, ] for i, test in enumerate(test_cases): result solution.groupAnagrams(test[input]) # 将结果列表转换为集合的集合便于无序比较 result_sets {frozenset(group) for group in result} expected_sets {frozenset(s) for s in test[expected_sets]} if result_sets expected_sets: print(f测试用例 {i1} 通过: input{test[input]}) else: print(f测试用例 {i1} 失败!) print(f 输入: {test[input]}) print(f 期望: {test[expected_sets]}) print(f 实际: {result}) print(f 实际(集合): {result_sets}) if __name__ __main__: test_group_anagrams()运行上述测试确保所有用例都能通过。这是工程实践中保证代码健壮性的重要一步。7. 常见问题与排查思路在实现和面试中你可能会遇到以下问题问题现象可能原因解决思路输出分组顺序与预期不同题目不要求分组顺序和组内顺序。使用集合Set比较结果而不是直接比较列表。哈希表键冲突错误分组1. 排序时未正确处理字符串如未转回字符串。2. 计数法构建键时未使用分隔符导致[11,0]和[1,10]都变成“110”。1. 确保key .join(sorted(s))或new String(sortedCharArray)。2. 计数法键使用“#1#0#11”格式。遇到非小写字母时计数法出错计数数组长度26只适用于小写字母。1. 先确认题目约束。若无约束改用排序法。2. 或使用大小为128ASCII或更大的数组。时间复杂度分析错误忽略了字符串排序或构建键的代价。牢记复杂度是 O(n * k log k) 或 O(n * k)其中 k 是字符串长度不是常数。内存占用过高1. 存储了不必要的中间数据如多个排序后的字符串副本。2. 在字符串很长时计数法的键字符串也很长。1. 优化代码及时释放不再需要的变量。2. 对于极长字符串考虑使用哈希算法如将计数数组哈希成一个整数但需注意碰撞风险。在Java中使用ListInteger作为键List的equals和hashCode可以用于HashMap但通常效率低于字符串。优先使用String或自定义类重写equals和hashCode作为键。8. 最佳实践与工程建议将这道题的解决方案应用到实际工程或应对更复杂面试时可以考虑以下方面1. 方法选择策略通用场景直接使用排序哈希表法。代码简洁可读性高适用于大多数面试和一般性编程任务。性能敏感场景如果已知字符串只包含小写字母且长度可能非常大优先使用计数哈希表法。字符集未知或很大如果字符串可能包含Unicode字符排序法仍然是安全的选择。计数法需要哈希表来存储字符计数实现会更复杂。2. 代码质量与可读性命名使用有意义的变量名如anagramMap、key、count。利用语言特性Python 使用defaultdict(list)或dict.get(key, [])简化代码Java 使用Map.computeIfAbsent或 Stream API。注释对算法关键步骤添加简要注释尤其是生成“键”的部分。3. 扩展思考如果要求分组内字符串按字典序输出在对每个分组列表添加到最终结果前对其进行排序即可group.sort()。如果输入规模巨大无法一次性加载到内存这是一个大数据问题。可以考虑外部排序或MapReduce思想将每个字符串的“键”计算出来然后按照“键”进行分布式排序和归并。如何判断两个字符串是否为字母异位词单个判断这就是本题的子问题。同样可以使用排序比较或计数比较时间复杂度 O(k log k) 或 O(k)。4. 关联题目与举一反三掌握本题的核心思想——“归一化”键可以解决一系列类似问题力扣 242. 有效的字母异位词判断两个字符串是否为异位词是本题的简化版。力扣 438. 找到字符串中所有字母异位词在滑动窗口中维护字符计数。力扣 187. 重复的DNA序列将DNA序列转换为数字编码作为键。任何需要根据数据的某种“特征”进行分组的场景都可以考虑设计一个“指纹”或“签名”作为哈希表的键。通过这道题我们深入理解了哈希表在分类和聚合问题中的强大威力。其核心模式是设计一个从复杂数据到简单键的映射函数使得具有相同特征的数据映射到相同的键从而利用哈希表O(1)的查找效率进行快速分组。从暴力法到哈希表法的优化过程也生动地展示了算法设计中“以空间换时间”和“预处理”思想的重要性。希望这篇详细的拆解能帮助你不仅AC这道题更能掌握其背后的通用解题范式在未来的算法学习和工程实践中游刃有余。