这次我们来看力扣LeetCode第49题“字母异位词分组”。这道题是面试和日常刷题中的高频考点它不要求你写出多么复杂的算法但非常考验对基础数据结构哈希表和字符串处理排序的灵活运用。很多朋友在初次接触时可能会陷入多层循环比较的误区导致时间复杂度飙升。本文的目标就是帮你彻底搞懂这道题从暴力解法到最优解一步步拆解并给出可以直接运行的代码。对于算法初学者或正在准备面试的同学这篇文章能让你快速掌握这道题的核心如何利用哈希表将查找字母异位词的时间复杂度从 O(N²) 降低到接近 O(N)。我们会先讲清楚什么是字母异位词然后分析为什么哈希表排序是这道题的最优解最后提供多种语言的代码实现和详细的复杂度分析。读完本文你不仅能轻松解决这道题更能深刻理解哈希表在解决字符串分组类问题中的强大威力。1. 核心能力速览在深入代码之前我们先快速把握这道题的关键信息和解决思路。能力项说明题目难度中等 (Medium)涉及数据结构哈希表 (HashMap / Dictionary)涉及算法思想排序、哈希映射时间复杂度O(NKlogK)其中 N 是字符串数组长度K 是字符串最大长度空间复杂度O(NK)用于存储哈希表和结果核心考察点1. 对“字母异位词”定义的理解2. 哈希表键的设计3. 排序或计数作为归一化手段最佳实践使用排序后的字符串作为哈希表的键变体与扩展可使用字符计数数组作为键适用于字符集有限的情况2. 适用场景与使用边界这道题虽然来自算法题库但其背后“分组”和“归一化”的思想在工程实践中广泛应用。适合谁算法初学者希望通过经典例题理解哈希表和排序的应用。求职面试者这道题是国内外大厂面试常见题掌握它能为面试增加筹码。需要处理文本数据的开发者例如对用户搜索词进行归类、对文档进行初步的相似性聚类等场景其核心逻辑与本题异曲同工。能解决什么问题核心是高效分组。给定一个杂乱无章的字符串数组如何快速地将所有字母异位词归到同一组暴力两两比较的方式在数据量大时完全不可行。本题的解法提供了一种“指纹”机制为每一类异位词生成一个唯一的“指纹”排序后的字符串或字符计数数组相同指纹的字符串自然就是一组。不适合什么场景对分组顺序有严格要求本题的输出顺序通常不做要求如果需要按某种特定顺序如组的大小、组内字典序输出需要额外处理。超大规模数据且字符串极长当字符串长度 K 非常大时排序操作 O(KlogK) 可能成为瓶颈此时可考虑使用固定长度的字符计数数组作为键其复杂度为 O(K)。需要处理Unicode等复杂字符集本题默认字符串由小写英文字母组成。如果字符集扩大排序方法依然有效但字符计数数组的大小需要调整。思想迁移学会这道题你可以轻松解决其他“找同类项”的问题例如给定一组数字将相同数字组成的数组归为一组数字异位。对一系列交易记录按交易类型和金额区间进行快速分组统计。3. 环境准备与前置条件要理解和运行本文的代码你只需要最基本的编程环境。我们不会部署复杂的服务但需要确保你的开发工具链就绪。1. 编程语言与版本本文代码示例将涵盖Python、Java和C三种语言。选择你熟悉的一种即可。Python: 推荐 Python 3.6 及以上版本。内置的collections.defaultdict和sorted函数会非常有用。Java: 推荐 JDK 8 及以上版本。需要熟悉HashMap、List和Arrays.sort()。C: 推荐 C11 及以上版本。需要熟悉std::unordered_map、std::vector和std::sort。2. 代码编辑器或IDE任何你习惯的编辑器都可以例如VS CodeIntelliJ IDEA (Java)PyCharm (Python)CLion (C)3. 力扣刷题环境可选但推荐如果你想在线验证代码可以直接访问 LeetCode 官网在题目页面编写代码并运行测试。题目链接通常为https://leetcode.com/problems/group-anagrams/或国内力扣对应页面。优势无需配置本地输入输出有丰富的测试用例。4. 核心依赖算法本身不依赖任何第三方库。核心操作是字符串排序将字符串转换为字符数组后进行排序。哈希表操作插入、查找。4. 问题分析与思路演化在直接看最优解之前我们先分析一下为什么不能使用最直观的暴力法以及最优解是如何一步步推导出来的。4.1 问题重述与理解题目给你一个字符串数组strs请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词由重新排列源单词的所有字母得到的一个新单词。例如“eat”、“tea”、“ate”互为字母异位词。输入输出示例输入: strs [eat, tea, tan, ate, nat, bat] 输出: [[bat],[nat,tan],[ate,eat,tea]]可以看到“eat”、“tea”、“ate”被分到了一组“tan”和“nat”一组“bat”自己一组。4.2 思路一暴力比较不可行最朴素的想法遍历每个字符串对于当前字符串再遍历它之后的所有字符串判断两者是否是字母异位词。判断方法可以是比较排序后的字符串是否相等或者比较字符计数是否一致。时间复杂度O(N² * KlogK) 或 O(N² * K)。其中 N 是数组长度K 是字符串长度。当 N 很大时例如 10⁴这个复杂度是无法接受的。为什么不行进行了大量重复的比较。“eat”和“tea”比较了一次“tea”和“ate”又比较了一次但它们明明属于同一类。4.3 思路二哈希表 排序最优解核心洞察属于同一组的字母异位词经过排序后会得到相同的字符串。 例如“eat”-“aet”“tea”-“aet”“ate”-“aet”。因此我们可以用这个排序后的字符串作为哈希表的键Key。哈希表的值Value是一个列表用于存放所有能生成这个键的原字符串。流程创建一个哈希表map键是字符串值是字符串列表。遍历输入数组中的每个字符串s。将s转换为字符数组排序再转回字符串得到key。检查key是否存在于map中。如果不存在则为该key创建一个新的空列表。将原字符串s添加到map[key]对应的列表中。遍历结束后将哈希表中所有的值即各个列表收集起来就是最终答案。复杂度分析时间复杂度O(N K log K)。遍历数组 O(N)对每个长度为 K 的字符串排序 O(K log K)。空间复杂度O(N K)。哈希表需要存储所有字符串。4.4 思路三哈希表 计数优化变体当字符串只包含小写字母时还有另一种“归一化”方法统计每个字母出现的次数然后将计数数组转换为一个唯一的字符串作为键例如“#1#0#0...#1”表示 a 出现1次z 出现1次。时间复杂度O(N K)。遍历字符串计数 O(K)构建键 O(26) 可视为常数。空间复杂度O(N K)。 这种方法在字符串较长、排序开销大时更有优势但代码稍显复杂。本文主要讲解更通用的排序法。5. 代码实现与逐行解析接下来我们分别用 Python、Java 和 C 实现“哈希表排序”的解法。每种实现都会附上详细的注释。5.1 Python 实现Python 的实现非常简洁充分利用了collections.defaultdict和sorted函数。from collections import defaultdict from typing import List class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: 将字母异位词分组。 :param strs: 字符串列表 :return: 分组后的列表 # 使用 defaultdict 避免判断 key 是否存在的繁琐操作 # 当访问不存在的 key 时会自动调用 list() 创建一个空列表 anagram_map defaultdict(list) for s in strs: # 关键步骤将字符串排序得到归一化的 key # sorted(s) 返回字符列表例如 sorted(tea) - [a, e, t] # .join() 将列表拼接回字符串例如 aet key .join(sorted(s)) # 将原字符串 s 加入到对应 key 的列表中 anagram_map[key].append(s) # 哈希表的所有 values 就是最终的分组结果 # 注意题目不要求组内或组间顺序直接返回即可 return list(anagram_map.values()) # 本地测试代码 if __name__ __main__: solution Solution() test_strs [eat, tea, tan, ate, nat, bat] result solution.groupAnagrams(test_strs) print(result) # 输出可能为[[eat, tea, ate], [tan, nat], [bat]] # 顺序可能不同但分组内容必须一致代码要点解析defaultdict(list)这是 Python 的一个利器。如果键不存在anagram_map[key]会自动初始化为一个空列表[]省去了if key not in map的判断。.join(sorted(s))这是生成键的核心。sorted(s)对字符串进行排序返回一个字符列表。.join(...)将列表无缝拼接回字符串作为哈希表的键。anagram_map[key].append(s)将当前字符串归入其对应的组。list(anagram_map.values())最终我们只需要哈希表中所有的分组列表。5.2 Java 实现Java 的实现需要显式地使用HashMap和Arrays工具类。import 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); // 将排序后的字符数组转换回字符串作为key String key new String(charArray); // 如果map中不存在这个key则创建一个新的列表 // computeIfAbsent 是Java 8的便捷方法 map.computeIfAbsent(key, k - new ArrayList()); // 将当前字符串添加到对应的列表中 map.get(key).add(s); } // 返回所有分组即map中的所有value // 注意题目要求返回 ListListString所以直接构造即可 return new ArrayList(map.values()); } // 本地测试 public static void main(String[] args) { Solution solution new Solution(); String[] testStrs {eat, tea, tan, ate, nat, bat}; ListListString result solution.groupAnagrams(testStrs); System.out.println(result); // 输出示例[[eat, tea, ate], [tan, nat], [bat]] } }代码要点解析MapString, ListString map new HashMap();定义哈希表键是排序后的字符串值是对应的异位词列表。char[] charArray s.toCharArray();和Arrays.sort(charArray);这是 Java 中对字符串排序的标准做法。map.computeIfAbsent(key, k - new ArrayList());Java 8 引入的优雅 API。如果key不存在则将其与一个新的ArrayList关联。new ArrayList(map.values())因为map.values()返回的是CollectionListString而我们需要ListListString所以用ArrayList构造函数包装一下。5.3 C 实现C 的实现涉及std::unordered_map和std::sort。#include vector #include string #include unordered_map #include algorithm using namespace std; class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { // 哈希表键为排序后的字符串值为原字符串数组 unordered_mapstring, vectorstring map; for (const string s : strs) { string key s; // 复制一份用于排序 // 对 key 进行排序 sort(key.begin(), key.end()); // 将原字符串 s 加入到对应 key 的 vector 中 map[key].push_back(s); } // 准备结果 vectorvectorstring result; // 遍历哈希表将每个分组加入结果 for (auto pair : map) { // pair.second 就是 vectorstring即一个分组 result.push_back(pair.second); } return result; } }; // 本地测试代码示例 int main() { Solution sol; vectorstring strs {eat, tea, tan, ate, nat, bat}; vectorvectorstring res sol.groupAnagrams(strs); // 输出结果... return 0; }代码要点解析unordered_mapstring, vectorstring map;C 中使用unordered_map作为哈希表。它的operator[]有个特性如果键不存在会自动插入一个默认构造的值对于vectorstring就是一个空向量。因此map[key].push_back(s)一行代码就完成了“检查-创建-添加”的所有操作。sort(key.begin(), key.end());C 中对字符串排序的标准方法。for (auto pair : map)遍历哈希表将每个分组pair.second加入结果集。6. 复杂度分析与性能观察理解算法复杂度是判断解法优劣的关键。我们来详细拆解一下。时间复杂度O(N K log K)N字符串数组strs的长度。我们必须遍历每一个字符串所以至少需要 O(N) 的时间。K单个字符串的最大长度。K log K对每个长度为 K 的字符串进行排序所需的时间。这是整个算法的瓶颈。相乘总时间就是遍历每个字符串并对其排序即 O(N * K log K)。空间复杂度O(N K)哈希表存储哈希表需要存储所有 N 个字符串。在最坏情况下没有异位词每个键对应一个字符串存储所有字符串需要 O(N K) 的空间K 为平均长度。排序开销排序过程通常需要 O(K) 的额外空间用于存储字符数组但这属于临时空间不影响整体的渐进空间复杂度。性能对比与优化思考当 K 很小例如 K 10排序开销 O(K log K) 很小此解法非常高效。当 K 很大例如 K 100排序可能成为负担。此时可考虑使用“计数排序”思想即思路三哈希表计数。因为本题说明字符串仅包含小写字母字符集大小为固定值 26。我们可以用一个长度为 26 的整数数组统计每个字符出现的次数然后将这个数组转换为一个格式化的字符串如“#1#0#0...#2”作为哈希表的键。这样处理每个字符串的时间复杂度降为 O(K 26) ≈ O(K)优于 O(K log K)。内存占用观察在本地测试或力扣平台运行时你可以通过简单的估算来感知内存使用哈希表本身有开销每个键值对都需要额外指针。存储了大量字符串如果字符串很长内存占用会显著增加。在工程实践中如果数据量极大可能需要考虑流式处理或分治策略但本题的常规数据范围下此解法内存完全足够。7. 功能测试与效果验证理论说完我们来实际验证一下代码的正确性。我们将设计多组测试用例覆盖典型、边界和特殊情况。7.1 测试用例设计典型用例题目给出的例子。输入[“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]预期输出三组[“eat”, “tea”, “ate”]、[“tan”, “nat”]、[“bat”]。组内和组间顺序不限。空输入测试函数对空数组的处理。输入[]预期输出[]无重复异位词每个字符串都是独立的。输入[“a”, “b”, “c”]预期输出[[“a”], [“b”], [“c”]]全部为同一异位词所有字符串排序后都相同。输入[“abc”, “bca”, “cab”, “acb”]预期输出[[“abc”, “bca”, “cab”, “acb”]]包含空字符串空字符串也是一个有效的字符串。输入[“”, “a”, “”, “ab”, “ba”]预期输出[[“”, “”], [“a”], [“ab”, “ba”]]。注意空字符串排序后仍是空字符串它们自成一组。长字符串测试排序性能和大字符串处理。输入[“abcdefghijklmnopqrstuvwxyz”, “zyxwvutsrqponmlkjihgfedcba”]预期输出这两个字符串是异位词应分到一组。7.2 验证步骤以Python为例你可以将下面的代码块复制到本地或力扣的代码编辑器中运行。def test_group_anagrams(): solution Solution() test_cases [ ([eat, tea, tan, ate, nat, bat], [[eat, tea, ate], [tan, nat], [bat]]), ([], []), ([a, b, c], [[a], [b], [c]]), ([abc, bca, cab, acb], [[abc, bca, cab, acb]]), ([, a, , ab, ba], [[, ], [a], [ab, ba]]), ([abcdefghijklmnopqrstuvwxyz, zyxwvutsrqponmlkjihgfedcba], [[abcdefghijklmnopqrstuvwxyz, zyxwvutsrqponmlkjihgfedcba]]), ] for i, (input_strs, expected) in enumerate(test_cases): # 注意结果中组的顺序和组内顺序可能不同需要特殊比较 result solution.groupAnagrams(input_strs) # 将结果和预期都转换为“集合的集合”来比较忽略顺序 result_set {frozenset(group) for group in result} expected_set {frozenset(group) for group in expected} if result_set expected_set: print(fTest case {i1} PASSED) else: print(fTest case {i1} FAILED) print(f Input: {input_strs}) print(f Expected: {expected}) print(f Got: {result}) if __name__ __main__: test_group_anagrams()运行与判断如果所有测试用例都输出PASSED说明你的算法逻辑基本正确。力扣的判题系统也是采用类似的方式忽略顺序只比较分组内容。8. 常见问题与排查方法在实现和调试过程中你可能会遇到以下问题。这里提供排查思路。问题现象可能原因排查方式解决方案输出结果分组错误例如该在一起的没在一起哈希表的键生成逻辑有误。打印每个字符串排序后的键。检查排序代码。在 Python 中确保是“”.join(sorted(s))而不是sorted(s)直接当键它是列表。在 Java/C 中确保排序操作正确应用于字符串副本。输出结果包含空组或丢失字符串哈希表初始化或添加元素逻辑有误。遍历时打印map的状态。在 Java 中检查是否使用了computeIfAbsent或手动put了新列表。在 C 中map[key]会自动创建一般没问题。在 Python 中使用defaultdict可避免此问题。代码在力扣上报“超出时间限制”使用了暴力解法O(N²)复杂度。检查你的算法是否嵌套了两层循环。务必采用哈希表解法将复杂度降至 O(N K log K)。内存占用过高1. 存储了不必要的中间数据。2. 字符串很长且数量多。检查是否在哈希表外还存储了排序前的字符串副本。1. 只存储必要的字符串引用在大多数语言中放入列表的是引用不是拷贝所以问题不大。2. 如果数据量极大考虑使用字符计数法避免存储排序后的长字符串键。处理包含大写字母或特殊字符的字符串时出错题目通常假设为小写字母但你的代码可能用于更通用场景。确认输入字符集范围。如果需处理大写字母排序方法依然有效。如果字符集包含 Unicode排序可能不按预期但通常仍可工作或需使用计数数组并扩大数组大小。返回类型不符合要求力扣编译错误函数签名或返回类型与题目要求不一致。仔细对照题目给出的函数签名。Python返回List[List[str]]。Java返回ListListString。C返回vectorvectorstring。9. 最佳实践与使用建议掌握一道题不仅要会写代码更要理解其精髓并能举一反三。以下是一些进阶建议1. 理解“归一化”思想这是本题最核心的思想。面对“分组”或“分类”问题思考如何为同一类元素设计一个唯一的“指纹”或“签名”。在本例中“排序后的字符串”就是一个完美的指纹。在其他问题中指纹可能是对一个数字数组排序后的数组。对一个二叉树序列化后的字符串。对一个图度序列或邻接矩阵的某种哈希。2. 选择最合适的键表示通用性优先排序法适用于任何可排序的元素序列通用性强。效率优先当元素范围有限且已知时如26个小写字母计数法字符统计数组效率更高因为它避免了排序的 O(K log K) 开销。空间权衡排序法需要 O(K) 或 O(K log K) 的临时空间和存储键的空间。计数法键的长度固定如26个计数但将其转换为字符串也可能占用空间。3. 代码简洁性与可读性利用语言特性如 Python 的defaultdict、sortedJava 的computeIfAbsentC 的unordered_map自动插入。这能让代码更简洁减少出错。命名清晰变量名如anagram_map、key比简单的map、k更能表达意图。4. 面试时的表达如果面试中遇到此题可以按以下步骤阐述澄清问题确认输入输出、字符集范围是否只有小写字母、是否区分大小写、空字符串如何处理。提出暴力解并分析缺点先给出两两比较的 O(N²) 解法指出其低效。引出优化思路“我们可以发现字母异位词排序后是相同的。利用这个性质我们可以用排序后的字符串作为哈希表的键…”给出最优解详细说明哈希表排序的流程、时间复杂度和空间复杂度。讨论变体“如果字符串只包含小写字母还可以用长度为26的计数数组作为键将时间复杂度优化到 O(NK)。”手写代码写出清晰、有注释的代码。测试口头跑一个简单例子。5. 关联题目练习为了巩固“哈希表分组”的思想建议练习以下力扣题目242. 有效的字母异位词本题的简化版判断两个字符串是否为异位词。438. 找到字符串中所有字母异位词在长字符串中寻找短字符串的异位词涉及滑动窗口和哈希表。249. 移位字符串分组分组条件从“排序后相同”变为“每个字符偏移相同距离后相同”但核心的“归一化”思想不变。字母异位词分组是连接哈希表、字符串处理和排序算法的经典桥梁。它的解法优雅而高效完美体现了计算机科学中“以空间换时间”和“寻找不变量”的思想。下次当你遇到需要将杂乱数据归类的场景时不妨先想一想我能不能为它们设计一个“指纹”