这次我们来看力扣LeetCode第49题“字母异位词分组”。这道题是面试和算法学习中的经典题目它不要求你掌握多么高深的数学理论核心是考察对基础数据结构哈希表和字符串处理排序的灵活运用。对于初学者来说这道题是理解“如何将复杂问题转化为已知操作”的绝佳范例。题目本身并不复杂给你一个字符串数组要求你将所有字母异位词即字母相同但排列不同的字符串组合在一起。关键在于你能否快速想到一个高效的解法并且用代码清晰地实现它。本文将直接切入主题先讲清楚这道题的核心解法思路再带你一步步完成代码实现、复杂度分析和边界情况处理。无论你是正在准备面试还是想巩固数据结构知识这篇文章都能让你彻底掌握这道题。1. 核心解法速览在深入代码之前我们先快速把握解决这道题的关键。它的核心在于找到一个“签名”使得所有字母异位词都具有相同的签名而非异位词则具有不同的签名。这样我们就可以用这个签名作为哈希表的键轻松完成分组。能力项说明与选择核心数据结构哈希表 (HashMap/Dict)。这是本题的绝对核心用于存储“签名”到“分组列表”的映射。关键操作字符串排序或字符计数数组。这是生成“签名”的两种主流方法。时间复杂度假设有n个字符串平均长度为k。排序法O(n * k log k)计数法O(n * k)。空间复杂度排序法O(n * k) 存储排序后的字符串计数法O(n * k) 存储结果和计数数组。代码实现难度低到中等。理解哈希表和签名生成逻辑后代码非常直观。适合场景面试高频题、算法入门练习、理解哈希表应用、学习字符串处理技巧。两种主流方法各有优劣排序法思路直观代码简洁计数法特别是使用字符计数数组在字符串较长或字符集有限如只包含小写字母时效率更高。本文将重点讲解这两种方法并给出清晰的代码对比。2. 问题理解与适用场景字母异位词Anagram是指由相同字母重排形成的单词或短语比如 “eat”, “tea”, “ate”。题目LeetCode 49就是要求我们将一个字符串数组中所有的字母异位词归类到同一个列表中。它能解决什么问题算法面试这是检验候选人是否掌握哈希表基础应用的典型题目。数据预处理在自然语言处理或文本分析中有时需要将词汇按构成字母归类。理解哈希思想学习如何为复杂对象设计“键”Key这是解决许多分组、去重、计数问题的通用技巧。它的边界在哪里输入限制题目通常不限制字符串长度和数组大小但我们的算法需要考虑通用性。字符集字符串可能包含 Unicode 字符而不仅仅是小写字母。通用解法需要能处理这种情况。输出顺序题目通常不要求组内或组间的顺序这给了我们实现上的灵活性。为什么它值得学习因为它完美展示了“化繁为简”的算法思想。面对一堆看似杂乱的字符串通过一个巧妙的转换排序或计数立刻就能看清它们内在的联系。这种通过映射来归类的思想在数据库的GROUP BY、分布式系统的数据分片等场景中都有广泛应用。3. 环境准备与思维工具解决算法问题不需要复杂的本地部署环境但需要清晰的思维工具。在动手编码前请确保你理解以下概念哈希表Hash Map一种能提供近乎常数时间复杂度O(1)进行查找、插入的数据结构。在 Python 中是dict在 Java 中是HashMap在 C 中是unordered_map在 JavaScript 中是Object或Map。字符串排序大多数编程语言都内置了字符串排序函数理解其时间复杂度为O(k log k)其中k是字符串长度。字符计数创建一个固定大小的数组例如26位对应26个小写字母遍历字符串统计每个字符出现的次数。这个计数数组或由其生成的字符串可以作为“签名”。心理准备不要一开始就追求最优解。可以先从最直观的排序法开始确保逻辑正确再思考优化。我们接下来将按照“思路分析 - 代码实现 - 复杂度分析 - 优化进阶”的顺序展开。4. 方法一排序 哈希表最直观这是最容易想到的方法。既然字母异位词排序后一定相同那么排序后的字符串就可以作为分组的“键”。4.1 算法步骤创建一个哈希表map键Key是排序后的字符串值Value是原始字符串组成的列表。遍历输入的字符串数组strs。对于每个字符串s先将其转换为字符数组排序再转回字符串得到key。检查key是否存在于map中如果不存在则以key为键创建一个新列表并将当前字符串s加入。如果已存在则直接将s添加到该key对应的列表中。遍历结束后哈希表map中所有的值即各个列表就是最终的分组结果。4.2 代码实现Pythonclass Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: # 初始化哈希表 anagram_map {} for s in strs: # 生成键将字符串排序 # sorted(s) 返回字符列表再通过 join 连接成字符串 key .join(sorted(s)) # 分组 if key not in anagram_map: anagram_map[key] [s] else: anagram_map[key].append(s) # 返回所有分组列表 return list(anagram_map.values())4.3 代码实现Javaimport java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { // 将字符串转换为字符数组并排序 char[] charArray s.toCharArray(); Arrays.sort(charArray); String key new String(charArray); // 分组 map.putIfAbsent(key, new ArrayList()); map.get(key).add(s); } // 直接返回哈希表中所有值的集合 return new ArrayList(map.values()); } }4.4 复杂度分析时间复杂度O(n * k log k)。其中n是数组strs的长度k是字符串的平均长度。我们需要遍历n个字符串并对每个字符串进行排序O(k log k)。空间复杂度O(n * k)。最坏情况下所有字符串都不是异位词哈希表需要存储n个排序后的字符串作为键。优点思路极其清晰代码简单适用于任何字符集的字符串。缺点当字符串较长时排序操作O(k log k)可能成为性能瓶颈。5. 方法二计数 哈希表更高效当字符串只包含小写字母时我们可以用计数法。用一个长度为26的数组统计每个字母出现的次数然后将这个计数数组转换成一个唯一的字符串如#1#2#0...#3作为哈希表的键。5.1 算法步骤创建一个哈希表map键是计数特征字符串值是原始字符串列表。遍历strs。对于每个字符串s初始化一个长度为26、值全为0的计数数组count。遍历s的每个字符ccount[ord(c) - ord(a)] 1。将count数组转换为一个特征字符串。例如[1, 1, 0, ...]可以转换为“#1#1#0...”。这一步至关重要因为列表本身不能直接作为哈希表的键在Python中需要转换为元组在Java中需要转换为String。用这个特征字符串作为key进行分组操作同方法一。5.2 代码实现Pythonclass Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: from collections import defaultdict # 使用 defaultdict 避免判断 key 是否存在 anagram_map defaultdict(list) for s in strs: # 初始化计数数组 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())5.3 代码实现Javaclass 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 sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#); sb.append(count[i]); } String key sb.toString(); map.putIfAbsent(key, new ArrayList()); map.get(key).add(s); } return new ArrayList(map.values()); } }5.4 复杂度分析时间复杂度O(n * k)。其中n是数组长度k是字符串平均长度。我们遍历每个字符串的每个字符进行计数O(k)然后生成一个固定长度26*数字位数的键O(1)。总体是O(n * k)。空间复杂度O(n * k)。存储结果和计数键。优点在字符串较长时O(n * k)通常优于排序法的O(n * k log k)。缺点只明确适用于字符集有限的情况如小写字母。如果字符集是 Unicode计数数组会非常大且稀疏效率可能反而不如排序法。代码稍复杂。6. 功能测试与效果验证理解了算法我们需要验证代码是否正确。下面设计几个测试用例。6.1 测试用例设计基础功能测试验证典型异位词能否正确分组。# 输入 strs [eat, tea, tan, ate, nat, bat] # 期望输出顺序不重要 # [ [bat], [nat,tan], [ate,eat,tea] ]边界测试空数组strs [] # 期望输出[]边界测试单个字符串strs [a] # 期望输出[ [a] ]边界测试所有字符串都相同strs [abc, abc, abc] # 期望输出[ [abc, abc, abc] ]边界测试没有异位词strs [abc, def, ghi] # 期望输出[ [abc], [def], [ghi] ]性能暗示测试长字符串# 包含较长字符串的数组用于思考两种方法的性能差异 strs [a*1000, b*1000, ...]6.2 如何验证你的代码本地IDE将上述测试用例输入你的Solution类运行并打印结果与期望输出对比。力扣平台直接在力扣题目页面编写代码使用自带的测试用例运行和提交。判断标准分组是否正确组内是异位词不同组的字符串不是异位词。输出列表的顺序不重要力扣的判题系统通常会进行排序比较。能通过所有基础用例和边界用例。6.3 常见错误排查键生成错误在计数法中忘记将列表转换为元组Python或生成特征字符串Java导致使用可变对象或数组作为键引发错误或分组失败。字符集假设错误在计数法中如果输入包含大写字母或数字仍然使用- ‘a’会导致数组越界。务必确认题目字符集范围或使用更通用的排序法。哈希表使用错误在添加新组时没有正确初始化列表导致None或null错误。7. 性能对比与选择策略现在我们对两种方法有了清晰的认识该如何选择对比维度排序法计数法时间复杂度O(n * k log k)O(n * k)空间复杂度O(n * k)O(n * k)代码复杂度低中适用字符集通用Unicode有限如小写字母长字符串性能较差受排序影响较好线性扫描短字符串性能很好常数小很好选择策略面试场景优先阐述排序法因为它思路直观易于解释。如果面试官追问优化再引出计数法并讨论其适用条件和优劣。这展示了你的思维层次。实际应用如果明确知道字符串只包含小写字母且字符串可能很长选择计数法。否则选择通用的排序法更为稳妥。竞赛场景根据题目给出的数据范围决定。如果k很大如k 10^4计数法的O(n*k)优势明显。一个重要的优化点在计数法中生成特征字符串时使用分隔符如#是必要的。直接拼接数字“110”会导致“1#10”和“11#0”混淆。使用StringBuilderJava或tuplePython可以安全、高效地创建键。8. 常见问题与排查方法在实现过程中你可能会遇到以下问题问题现象可能原因排查方式解决方案输出结果分组错误异位词没分到一起。1. 键生成逻辑错误。2. 哈希表的值不是列表而是被覆盖了。打印每个字符串生成的key检查是否相同的异位词产生了相同的key。检查排序或计数代码。确保哈希表的值是列表并使用append或add方法添加元素。在Python计数法中出现TypeError: unhashable type: ‘list‘。试图用列表count直接作为字典的键。查看错误行确认是否将list用作dict的键。将列表转换为元组key tuple(count)。在Java计数法中长字符串输入导致性能不佳。可能使用了String拼接来生成键在循环中创建了大量中间对象。检查键生成部分的代码。使用StringBuilder来构建特征字符串。计数法对于包含大写字母的输入报错数组越界。假设字符全是小写使用了c - ‘a‘。确认输入字符集。1. 改用排序法。2. 或扩大计数数组大小如128对应ASCII使用c直接作为索引需注意内存。力扣提交显示“超出时间限制”。1. 算法时间复杂度太高。2. 在循环内进行了不必要的复杂操作。分析你的代码时间复杂度。对于大数据集排序法可能较慢。尝试切换到计数法。检查是否有冗余的循环或转换。输出结果的顺序与示例不同导致判题失败。力扣判题通常不关心顺序但有时会进行排序比较。阅读题目描述确认是否对输出顺序有要求。通常无需处理。如果判题失败可以尝试对最终结果的每个子列表进行排序或对整个结果列表排序。9. 最佳实践与扩展思考掌握了基础解法后我们可以思考如何写得更好以及相关问题。9.1 编码最佳实践使用defaultdict或putIfAbsent这可以简化代码避免冗长的if-else判断键是否存在。如上文Python示例所示。明确变量名使用anagram_map、key、count等有意义的变量名提高代码可读性。考虑字符集在面试中如果使用计数法一定要主动说明“假设字符串只包含小写字母”。这体现了你的严谨性。复杂度分析养成习惯写完代码后主动分析时间、空间复杂度。9.2 扩展与变式变式1分组字母异位词字符集为Unicode此时计数数组会非常大。可以使用排序法或者使用HashMapCharacter, Integer来动态存储计数Python中用collections.Counter然后将这个计数映射转换为可哈希的键如将Map的条目排序后转为字符串。变式2找出所有字母异位词对这是本题的简化版只需要找出是异位词的两个字符串。可以使用类似的哈希表思路但值存储索引或单个字符串即可。关联题目LeetCode 242. 有效的字母异位词本题的简化版判断两个字符串是否为异位词。是解决本题的基础。LeetCode 438. 找到字符串中所有字母异位词使用滑动窗口和计数数组是计数法的另一种经典应用。9.3 从这道题学到什么哈希表的威力它将分组操作的复杂度从暴力法的O(n^2 * k)降低到了O(n * k log k)或O(n * k)。设计键Key的艺术许多复杂分组问题如分组移位字符串、分组拥有相同字符的字符串的核心都在于如何设计一个合适的键。时间与空间的权衡排序法通用但稍慢计数法高效但有字符集限制。没有绝对的好坏只有适合的场景。这道题就像一把钥匙帮你打开了“如何利用哈希表解决分组问题”的大门。它的解法模式非常固定遍历 - 为每个元素计算一个特征键 - 用哈希表根据键分组。掌握这个模式你就能解决力扣上一大批类似的题目。建议你立即打开力扣找到第49题将本文的两种方法亲手实现一遍并尝试解决上面提到的关联题目巩固这一重要的算法思想。