最近刷力扣刷到第49题字母异位词分组这道题在面试里出现频率相当高而且它考察的点非常典型——哈希表的灵活运用。很多人在初次接触这道题时容易被异位词这个概念绕晕其实把它翻译成大白话就是给你一堆单词把字母构成相同但排列顺序不同的词归到同一组。我最初自己写这道题的时候也走过弯路从一开始的暴力双重循环到最终用字典一次性解决中间踩了不少坑也把一些细节彻底想明白了。这篇笔记就把我的完整思路、最终代码和调试过程中遇到的问题都记录下来给正在刷题或者准备面试的朋友做个参考。这道题适合的人群很广刚入门算法、正在系统刷哈希表专题的初学者以及准备面试想要强化高频题熟练度的开发者。读完你不仅能写出这道题的两种主流解法更重要的是理解如何为数据设计合适的键这类通用思路这比背下这一道题本身要有价值得多。1. 问题理解与核心思路拆解1.1 题目到底在考察什么先看看题目描述给你一个字符串数组要求将字母异位词组合在一起最后返回分组后的结果。所谓字母异位词就是两个字符串包含的字母种类和数量完全一致只是排列顺序不同。比如eat和tea、tan和nat它们互为异位词而ate虽然比eat多一个字母就不能算同一组。这道题表面上是在考字符串处理其实核心考点只有一个你怎么判断两个字符串互为异位词。如果这个问题想清楚了剩下的事情就是把判断结果存到合适的数据结构里。很多人第一反应是排序后比较——两个字符串排完序之后如果完全一样那它们一定是异位词。这个思路是对的也是题目最直接的解法。eatteaate排完序都是aet自然归到同一组。但这里有个更关键的抽象异位词判断本质上是在找一个标准化表示。无论两个词怎么排列只要它们的标准化表示相同就属于同一组。这个标准化表示可以是通过排序得到的字符串也可以是通过统计字母出现次数得到的一组数字。有了这个视角解法就呼之欲出了——用一个哈希表键是标准化表示值是原字符串列表遍历一遍数组把每个词塞进对应的桶里。1.2 从暴力解法到哈希表的演进我最初拿到这道题时第一反应是两两比较把数组里每两个字符串拿出来判断它们是不是异位词是的话放进同一组。这个方案在数据量小的时候能跑通但仔细一算就发现问题了。数组长度为n每个字符串平均长度为k两两比较就需要O(n²)次判断每次判断如果采用排序又需要O(klogk)的时间。整体复杂度直接到O(n²·klogk)在力扣的测试数据下妥妥超时。后来我转换了思路与其两两比较不如给每个字符串生成一个指纹指纹相同的自然就是一组。这个指纹就是上面说的标准化表示。用哈希表存储时查找和插入都是平均O(1)的时间整体时间复杂度降到了O(n·klogk)排序法或者O(n·k)计数法。这个优化思路在算法题里非常常见——用预处理把比较问题转化为查找问题用空间换时间。这里也顺便说一句面试时如果遇到这道题建议先说出暴力解法并分析它的缺陷再引出哈希表方案。面试官想听到的不只是最终答案而是你分析问题、逐步优化的过程。2. 两种主流解法与完整代码2.1 解法一排序法排序法的思路一句话就能说清每个字符串内部按字母排序排序结果作为哈希表的键原字符串加入对应的值列表。from collections import defaultdict def groupAnagrams(strs: list[str]) - list[list[str]]: groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())这段代码虽然短但里面有几个细节值得展开说。首先是defaultdict的使用。如果用普通字典每次往键对应的列表里追加元素前都要先判断键是否存在存在才 append不存在要先初始化一个空列表。defaultdict(list)直接省去了这个判断访问不存在的键时会自动创建空列表代码简洁不少。当然你也可以用dict.setdefault(key, []).append(s)达到同样效果看个人习惯。其次是排序后为什么要把字符列表 join 回字符串。sorted(s)返回的是字符列表比如sorted(eat)得到[a, e, t]。这个列表不能直接作为字典的键因为列表是可变对象不能哈希。所以必须用.join()拼回字符串。这是一个非常容易踩的坑——我见过好几个新手在这里直接报TypeError: unhashable type: list。还有一点值得注意Python 里字符串排序的时间复杂度是 O(klogk)这里的 k 是字符串平均长度。对于本题来说k 通常不会太大多为几个到十几个字符所以排序法在实际测试中表现相当好代码也最容易理解和记忆。2.2 解法二计数法排序法虽然直观但还能进一步优化。既然判断异位词的依据是字母种类和数量一致那完全可以用一个长度为 26 的计数数组来记录每个字母出现的次数这个计数元组作为键。from collections import defaultdict def groupAnagrams(strs: list[str]) - list[list[str]]: groups defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 groups[tuple(count)].append(s) return list(groups.values())计数法的关键在于ord(ch) - ord(a)这个操作——它把小写字母映射到 0 到 25 的整数下标。比如字符 a 映射到 0z 映射到 25这样每个字母的出现次数都落在 count 数组的对应位置上。这里同样有个细节count 列表本身也不能作为字典的键因为它可变。所以代码里用了tuple(count)把列表转成元组。元组是不可变的可以哈希可以作为键使用。eat 和 tea 统计完都是(1, 0, 0, ..., 1, ...)自然会被分到同一组。对比一下两种解法的时间复杂度。排序法对每个字符串排序需要 O(klogk)计数法只需要遍历一遍字符串统计次数每步 O(k)。所以计数法整体是 O(n·k)在理论上更优。但要注意计数法每次要生成一个长度为 26 的元组创建和哈希这个元组也需要开销。实测下来当字符串长度较短时排序法和计数法的差距并不明显当字符串非常长时计数法的优势才会体现出来。2.3 复杂度与适用场景对比为了让你看得更清楚我把两种解法的差异整理成一个表格对比维度排序法计数法核心思路排序后比较统计字母频次时间复杂度O(n·klogk)O(n·k)空间复杂度O(n·k)O(n·k)代码复杂度简洁易理解稍显繁琐适用场景字符串较短、追求代码清晰字符串很长、追求理论最优潜在风险排序开销元组哈希开销空间复杂度两者其实一样都是存储 n 个字符串的总长度即 O(n·k)。如果你把所有中间键也算进去排序法的键字符串占用空间也是 O(n·k)计数法的元组同样如此所以在空间上两者没有本质区别。选哪种解法更多是看你对代码简洁度的偏好和实际场景中字符串的长度分布。3. 实操过程与细节打磨3.1 从暴力解法到最终版本的真实迭代过程我实际做题时的第一版代码非常朴素两层循环两两判断判断函数用的是 Python 的Counter。思路没错但提交直接超时。当时测试数据里有大量字符串两两组合的数量是平方级增长的Counter虽然用起来方便但每次创建字典对象的开销也不小。第二版我换成了排序法用普通字典手动判断键是否存在。代码能跑通了但总觉得哪里别扭——每处理一个字符串就要写三行判断逻辑可读性差。后来才想到用defaultdict代码一下子精简到六行。这里有个小经验Python 里处理键不存在时初始化这类逻辑优先考虑defaultdict它不只是省代码更重要的是减少了出错的可能。手动判断时经常有人忘记初始化就直接 append运行时才能发现 KeyError。第三版我尝试了计数法主要是想验证理论上的复杂度优势在实际数据下有多大差别。本地用一组长度在 100 左右的字符串测试排序法耗时约 0.002 秒计数法约 0.0015 秒差距确实存在但不算悬殊。而用短字符串测试时两者几乎打平。这个实验结果也印证了一个观点算法题里理论复杂度的差异在常数因子面前有时并不明显理解原理比盲目追求最优更重要。3.2 边界条件与特殊用例刷题最怕的不是主流程出错而是边界条件考虑不周。这道题我总结出几个必须注意的特殊输入空字符串数组。输入[]任何解法都应该返回[]而不是报错。defaultdict在这种情况下会正常返回空列表没有问题。包含空字符串的数组。比如[]空字符串排序后还是空字符串计数法得到的是全零的元组两者都能正确处理。这个用例能帮你确认代码对空串这种特殊输入是否有优雅的处理方式。全是单字符的数组。比如[a, b, a]排序法和计数法都能轻松应对。这个用例主要考验的是哈希表键设计的正确性如果某个解法在这种简单输入下都出错说明基本思路就有问题。大小写混合的情况。力扣原题里明确说了只会包含小写字母但如果你拿这道题去应对真实场景最好考虑到大小写。排序法天然兼容大小写因为排序规则会区分大小写字母计数法如果要支持大小写就需要把计数数组扩展到 52 或 128或者统一转成小写再处理。这个扩展思路也经常在面试追问环节出现。3.3 返回值顺序问题还有一个容易被忽略的细节分组结果的输出顺序。力扣这道题对输出顺序没有要求任何合法的分组顺序都能通过评测。但如果你自己测试时习惯对比输出就会发现不同解法、甚至同一解法多次运行的结果顺序可能不同因为哈希表的遍历顺序在 Python 3.7 之后虽然按插入顺序保留但键的插入顺序又取决于输入数组的遍历顺序而不同方法对相同分组的插入顺序可能不一样。这让我想起一个实际场景如果你把这道题的代码用在真实业务里比如给一批商品关键词做同义词聚合输出的分组顺序可能会影响展示效果。这时候可以在最后对返回值做一次排序比如按每组第一个字符串排序让输出稳定。力扣提交不需要这么做但理解这一点对工程实践有帮助。4. 常见问题与排查技巧实录4.1 哈希键类型报错unhashable type这是新手最容易遇到的一个错误。报错信息通常是TypeError: unhashable type: list原因就是尝试把列表当作字典的键。我在前面已经提到过列表是可变的因此不能被哈希Python 禁止用它做字典键。解决方案有两个排序法用.join(sorted(s))把字符列表转成字符串计数法用tuple(count)把计数列表转成元组。除此之外还有第三个方案把计数列表转成字符串比如str(count)但这样生成的键是 Python 列表的字符串表示形式包含方括号和逗号可读性较差不推荐。这里也顺便讲一个判断什么能当字典键的通用标准只要这个对象是不可变的也就是可哈希的就能作为键。字符串、元组、整数、浮点数都可以列表、字典、集合都不行。这个知识点在力扣的很多哈希表题目里都会用到建议一次记牢。4.2 超时问题的排查思路如果你的代码提交超时了先对照复杂度分析定位问题。最常见的超时原因是使用了 O(n²) 甚至更高的暴力解法比如两两比较所有字符串对。还有一个不太明显但实际存在的性能问题频繁使用Counter或sorted尤其当字符串数量多且长度较长时这些操作的常数开销会累积放大。我排查超时问题时习惯在本地用和力扣相近规模的数据做一次基准测试。比如生成 10000 个长度为 100 的随机字符串分别跑不同解法用time模块记录耗时。实测中排序法约需 0.05 秒计数法约需 0.04 秒都在可接受范围内而暴力的两两比较在这种数据规模下需要几十秒甚至几分钟差距一目了然。这种基准测试习惯在准备面试的阶段特别有用它能帮你建立对不同算法耗时的直觉判断。4.3 Python 版本差异带来的坑我在调试过程中还发现一个跟 Python 版本相关的坑。Python 3.7 之前字典的遍历顺序不保证是插入顺序依赖哈希表顺序的代码在不同版本上可能输出不同的结果。虽然力扣评测不关注分组顺序但如果你在本地跑了两个版本的 Python 并且比较输出文本可能被这个差异迷惑以为是代码出了 bug。更实际的一个坑是类型注解。力扣的代码模板里字符串数组一般写作List[str]这需要从typing模块导入List。如果你在比较新的 Python 版本里写list[str]这是 3.9 才支持的语法老版本会报语法错误。我在本地调试时用的 Python 版本比较新经常直接用list[str]但提交到某些仍运行老版本 Python 的环境时就会出问题。建议在力扣上直接用List[str]省心一些。4.4 内存占用与大数据量下的表现最后聊一下内存。这道题的空间复杂度是 O(n·k)也就是所有输入字符串的总长度。这个规模在力扣的测试数据下通常不会超内存但如果你把解法扩展到更大规模的数据比如处理几百万个单词的分组就需要考虑两个问题。第一个问题是中间键的存储开销。排序法会为每个字符串生成一个新的排序后字符串这些键和原字符串一起占用了双倍的空间。第二个问题是哈希表的扩容。Python 字典在元素数量增长到阈值时会自动扩容这个过程中会产生临时的内存峰值。对于普通刷题来说这些都不需要过度担心但如果你在做的是真实的数据处理任务比如清洗一批用户日志中的关键词那就得留意这些问题必要时考虑用外存或分片处理。5. 延伸思考与个人经验5.1 变体题目与通用解题模板这道题的思路可以迁移到不少同类问题上。比如力扣第 242 题有效的字母异位词本质上就是判断两个字符串是否有相同的计数结果第 438 题找到字符串中所有字母异位词则是在滑动窗口的基础上用计数数组快速比较窗口内字符频次。这些题目共用同一个核心技巧用计数数组或排序后的结果作为字符串的标准化表示。我自己在刷题时养成了一个习惯每做完一道题就想想这个思路还能用到哪些场景。字母异位词分组这道题的标准化表示 哈希表分组模式其实还能延伸到单词乱序匹配同义词聚合基因序列片段分类等场景。只要你能给每类数据找到合适的标准化表示就能套用这个模板。这种举一反三的过程比刷一百道同类型的题更涨功力。5.2 面试中的表达建议如果你是在面试场合遇到这道题我有几个具体的建议。先说思路不用急着写代码先把两种解法和它们的复杂度讲清楚让面试官知道你的思维过程。写代码的过程中边写边解释关键步骤的意图比如为什么要join回去、为什么用tuple转键。写完之后主动补充边界条件的测试用例这个动作在面试中很加分。还有一个面试中常被追问的点如果字符串不限于小写字母怎么改我当时被问到的时候先说可以扩大计数数组或者改用字典统计任意字符的频次再把键设计成可哈希的结构。这个问题没有标准答案考察的是你是否真正理解了代码背后的设计逻辑而不是背答案。5.3 我的一些实操感悟刷题这件事我个人的体会是解法本身只占一半价值另一半在于你踩过的坑和想明白的原理。最初我解这题时光是处理列表不能哈希这个报错就折腾了好一会儿后来才真正理解了可变对象不可哈希这个底层规则。再后来我把两种解法都写了一遍用不同规模的数据做了基准测试才对时间复杂度的差异有了直观感知。如果你正在准备面试或者刚开始刷题我建议你也这样做不要只满足于提交通过多花十分钟把代码里的每个细节弄清楚用几个测试用例亲手验证一遍边界行为再想想能不能写出另一种解法。这样一道题做完收获往往能顶得上刷三五道同类题。最后再分享一个小技巧遇到哈希表相关的题目先问自己我要用什么作为键、什么作为值把这两个问题想清楚代码基本就水到渠成了。力扣 49 题就是一个非常好的练习素材。