去年帮团队做技术面试模拟我随手在 LeetCode 上挑了一道题当考题题目就是“字母异位词分组”。三个候选人里有两个能脱口而出用哈希表可真到了白板上写代码卡住的点几乎一模一样不知道拿什么当 key。这道题表面上只是把字符串按异位词关系归组可一旦你把思路落到代码层面会发现里面的取舍、边界条件、坑位比想象中多得多。这篇文章我就从那次面试复盘开始把解题思路、两种主流写法、踩坑记录以及这题背后真正值得带走的工程思维完整拆开聊一遍。1. 一次面试复盘题面很短坑位不少1.1 先搞清楚我们到底要分什么组字母异位词英文叫 anagram指的是两个字符串包含的字符种类和数量完全一致只是排列顺序不同。比如eat、tea、ate都是由一个e、一个a、一个t组成的顺序不一样而已它们就是一组异位词。而tan和nat又是另一组因为它们的字符构成是t、a、n。题目输入是一个字符串数组比如[eat, tea, tan, ate, nat, bat]期望输出是按异位词关系分组后的二维数组顺序无所谓[ [eat, tea, ate], [tan, nat], [bat] ]注意bat只有自己一个也得单独作为一组输出。这个细节很多人第一遍会看漏等到写测试用例的时候才发现漏了单个元素的组。这道题在 LeetCode 上是第 49 题标注难度是中等但实际上它的入门门槛很低核心思路可能小学奥数水平就能理解——两个人名字字母相同、调换顺序本质上就是同一组嘛。真正的分歧在于你怎么在程序里快速判断任意两个字符串是不是异位词并且把它们放进同一个集合里。1.2 “分组”两个字才是真正的题眼我复盘那次面试时发现候选人普遍有一个共同问题他们在纠结“如何判断两个字符串是不是异位词”比如排序后比较是否相等或者用两个哈希表数一下字母频次再比。这个方向当然没错但如果你把思路局限在“两两比较”复杂度就会变得非常难看——N 个字符串两两比较一遍就是 O(N²)哪怕每次比较很快数据一多也扛不住。正确的切入点是“分组”这个词。听到分组第一反应应该是我需要一个映射关系把同一类的元素映射到同一个标识上。这就意味着要建哈希表key 是某种“统一的标识”value 是对应的字符串列表。于是问题从“两两比较”变成了“给每个字符串找一个分组标识”复杂度直接被压成了线性级别的单次遍历。这一步思维转换就是这道题最核心的考点。从算法角度讲它考的不是排序、不是哈希技巧本身而是你有没有意识到“分组”这个动作天然就该用哈希表去建模。后面的所有解法其实都是在回答同一个问题什么样的 key 能让异位词映射到一起同时让非异位词不撞车。2. 排序键法把乱序字符拉回同一条轨道2.1 排序为什么能让异位词自动“对暗号”最容易想到、也最稳的方案是排序键法。思路就一句话把每个字符串内部的字符按字典序排序把排序结果当作 key。为什么它能成立因为如果两个字符串是异位词它们的字符构成完全相同排序之后的结果必然一模一样。反过来如果两个字符串排序后相同说明它们的字符构成完全相同必然是异位词。这是一个等价的充要条件不会漏也不会错。打个比方你把每个组的人都拉去军训规定所有人必须按身高从低到高站成一排。原来乱糟糟站队的同一组人站完之后队伍形态是一样的不同组的人哪怕身高组成只差了一点点站出来的队伍形态也一定不同。排序就是那把“强制整队”的尺子。还有个容易被忽略的好处排序后的字符串天然是无碰撞的。因为两个不同构成的字符串排序结果一定不同不存在“误分到同一组”的可能性。这一点在面试回答里非常加分你可以明确告诉面试官这个方案的 key 是确定性的不存在哈希碰撞导致的语义错误。2.2 Python 实现几十行以内就能跑通from collections import defaultdict def group_anagrams(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(list)省掉了手动判断 key 是否存在的步骤每次计算完 key 直接 append 就行。整个函数的返回值是把字典的所有 value 转成列表每一组异位词自然就是一个子列表。针对题目给的示例这段代码的执行过程是strs [eat, tea, tan, ate, nat, bat] eat - sorted(eat) - [a, e, t] - aet - {aet: [eat]} tea - sorted(tea) - [a, e, t] - aet - {aet: [eat, tea]} tan - sorted(tan) - [a, n, t] - ant - {aet: [...], ant: [tan]} ate - sorted(ate) - [a, e, t] - aet - {aet: [eat, tea, ate], ant: [tan]} nat - sorted(nat) - [a, n, t] - ant - {aet: [...], ant: [tan, nat]} bat - sorted(bat) - [a, b, t] - abt - {aet: [...], ant: [...], abt: [bat]}最终输出[[eat, tea, ate], [tan, nat], [bat]]和题目期望完全一致组内字符串的相对顺序取决于遍历顺序。2.3 排序键法的性能画像假设字符串数组里有 N 个字符串平均每个字符串长度是 K。排序的时间复杂度是 O(K log K)遍历 N 个字符串之后整体时间复杂度就是 O(N × K log K)。额外的空间消耗主要是每一组的存储和哈希表的 key整体大概 O(N × K)。这个复杂度在 LeetCode 的数据规模下完全没问题几十毫秒就能跑完。即便是实战项目中处理几万个短单词排序键法也足够快。选择排序键法的最大优势是简单、鲁棒你不用假设字符集大小写混着来也行甚至字符串里出现数字、下划线、中文只要你用sorted()对字符排序异位词判断依然成立。这得益于 Python 对任意 Unicode 字符都能排序。但我必须补一句排序操作本身是有开销的尤其当单个字符串特别长比如几万字符的文本片段排序一次的成本会明显上升。这时候你可能更想要下面这种不用排序的计数键法。3. 计数键法把排序换成字符频率指纹3.1 用频率表当“身份证”既然异位词的字符构成完全相同那我不需要排序直接统计每个字符出现的次数不就行了这个统计结果就是字符串的“字符频率指纹”。以小写字母为例我可以开一个长度为 26 的数组下标从 0 到 25 分别对应a到z遍历字符串每遇到一个字符就在对应位置加 1。最后把这个数组转成元组tuple当作 key 存进哈希表。为什么用元组而不是列表因为 Python 里列表是可变的不能作为字典的 key。元组不可变、可哈希天然满足字典键的要求。这一点不少面试候选人会当场卡住写了个列表当 key一运行就报TypeError: unhashable type: list。3.2 代码实现基础版与通用版标准的小写字母版写法from collections import defaultdict def group_anagrams(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)的作用是把字符ch映射到 0-25 的整数下标。比如a的 ord 值是 97a - a算出 0z - a算出 25。这是很多语言里处理英文字母的惯用技巧。上面这个写法有一个隐含假设字符串只包含小写字母。如果输入里混进了大写字母、数字或者中文count 数组的下标会越界或者错位。实际刷题时题目一般会明确说明只包含小写字母但你要是想写一个更通用的版本可以这样from collections import defaultdict def group_anagrams_general(strs: list[str]) - list[list[str]]: groups defaultdict(list) for s in strs: freq defaultdict(int) for ch in s: freq[ch] 1 key frozenset(freq.items()) groups[key].append(s) return list(groups.values())这个版本用字典记录每个字符的频次再用frozenset(freq.items())作为 key。frozenset是可哈希的而且不关心频次项的排列顺序天然适合当键。当然通用版的构建成本比数组版本高一些在 LeetCode 的 26 个小写字母场景下没必要用。3.3 两种主流解法怎么选看数据说话到了这一步你手上有两条路排序键法和计数键法。它们各有优劣我把关键维度列出来对比维度排序键法计数键法核心操作对每个字符串排序统计每个字符频次时间复杂度O(N × K log K)O(N × K)实现难度极低两三行中等要理解数组下标映射字符集假设几乎无限制数组版默认只支持小写字母键是否可读可读排好序的字符串不可读是一串数字适用场景短字符串、通用字符集长字符串、固定字符集从我自己的刷题习惯来说LeetCode 上我优先写计数键法因为字符串长度短的时候两者速度都很快但计数法的时间复杂度更好对面试官来说也更能体现你对“字符频率”这个概念的理解。而实际项目的 text processing 场景里如果字符集不确定、字符串也不长我会选排序键法省心不容易写错。4. 实战踩坑记录三个容易翻车的角落4.1 空字符串到底算不算一组异位词分组里空字符串是个容易被忽略的特殊输入。的排序结果还是它的字符频率数组是全零所以会形成一个单独的组。这没问题关键是你的代码得能正确处理它而不是在sorted()或者count[ord(ch) - ord(a)]的地方报错。另一个类似的边界是数组里存在重复字符串比如[a, a]。这时候两个a应该被放进同一个组输出[[a, a]]。如果输出里出现了两个独立的[a]说明你的分组逻辑写错了。这个用例我建议你写代码前先在心里过一遍因为它能同时检验你对“同一字符串多次出现”的处理是否正确。4.2 哈希键会不会碰撞要区分两种“碰撞”这里有个概念特别容易搞混。我们设计的 key排序字符串或频率元组会不会把两个不同的异位词分组错误地映射到一起不会。这是因为排序键法和计数键法都满足一个性质key 相同当且仅当两个字符串是异位词。排序字符串是字符重排后的唯一形态频率元组是字符分布的唯一刻画两者都是双射关系天然不存在语义碰撞。另一种“碰撞”是哈希表底层的哈希冲突即不同 key 的 hash 值碰巧相同。这是字典本身要处理的问题Python 的 dict 内部会用开放寻址或链地址法解决轮不到你操心。你要担心的是前者——千万别设计出多对一的 key。比如有个常见的错误想法直接统计字符总个数当 key那ab和cd长度都是 2会被错误地分到一组这显然是错的。4.3 大写字母和混合字符集题目如果说只包含小写字母那数组版计数法是最快路径。但如果你在真实项目里复用它遇到Eat和ate这种大小写混排的字符串计数法会认为它们是不同的字符因为ord(E)和ord(a)的差值完全不同。处理方式有几种最简单的是在统计前统一lower()把英文字母全部转成小写。这样Eat的 key 就会和ate一致。还有一种做法是只过滤保留字母字符忽略空格和标点这在处理英文文本时很常见。我自己在实际处理搜索词的时候通常会做一层清洗小写化 去标点 压缩连续空格然后才去统计频次。要是你直接拿原始字符串套用 LeetCode 解法结果往往会让你怀疑人生。4.4 一个冷门但高效的黑科技质数乘积法既然提到了 key 的设计我再讲一个在面试里能惊艳全场的技巧用 26 个质数分别对应 26 个字母比如a2、b3、c5、d7……每个字符串的 key 就是所有字母对应质数的乘积。PRIMES [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ] def group_anagrams_prime(strs: list[str]) - list[list[str]]: groups defaultdict(list) for s in strs: product 1 for ch in s: product * PRIMES[ord(ch) - ord(a)] groups[product].append(s) return list(groups.values())质数乘积法的依据是算术基本定理任何正整数都可以唯一分解成质数的乘积顺序无关。aab和aba都会算出2 × 2 × 3 12而任何其他字母组合都不可能算成 12。它的时间复杂度降到了 O(N × K)而且代码很短看起来非常聪明。但我要提醒你这个方案有一个隐藏风险当字符串很长时乘积会指数级膨胀。在 Python 里整数是任意精度的不会溢出所以没事。但你要是用 Java 的int或 C 的long很快就会溢出成错误结果。所以这个技巧更适合面试时作为思路补充真正写产品代码我不会用它除非能严格限制字符串长度。以前有次我用 Java 跑这个思路一个 20 来字符的字符串乘积就已经超过了long的安全范围差点背锅。别问我为什么记得这么清楚。5. 从一道题抽象出一种通用思维归一化键5.1 这道题真正想让你带走的东西很多人刷题只记结论刷完“字母异位词分组”下一次遇到“判断两个字符串是否互为异位词”能想起来再遇到“将乱序字符串分组”又想半天。其实这三类问题都是同一个套路归一化键。什么叫归一化键就是在一个分组问题里你为每一个元素计算一个与它一一对应的标准特征让同一组的元素得到完全相同的特征值。然后把特征值作为哈希表的 key整个分组问题就变成了“遍历一次 按 key 归类”。这个套路绝不仅限于异位词。比如你有一堆文件名想把扩展名相同的归到一起key 就是扩展名你有一堆订单想按月归组key 就是订单时间的年月部分你在做语音识别后处理想把同一句话的不同口音文本归组先做一次拼音或音标归一化再拿归一化结果当 key。本质上都是一回事。理解了这一层“字母异位词分组”就不只是一道孤立的题了它是一类“把复杂对象投影到标准空间再分组”问题的原型。面试官后续追问的很多变种题都是在换着花样考这个点。5.2 跟它捆在一起考的兄弟题目LeetCode 里和异位词相关的题有好几道难度递增值得一起刷242. 有效的字母异位词只问你两个字符串是不是异位词不需要分组。用计数键法就是 O(N) 一次遍历是最简单的热身题。438. 找到字符串中所有字母异位词在长串 s 里找短串 p 的所有异位词子串起始位置。这道题要用滑动窗口加频率数组窗口右移时更新字符频次和分组题结合得很好。49. 字母异位词分组就是本文这道题四边形齐了。如果你把这三道题连着刷会发现它们的共同核心都是“字符频率的比较”。区别只在于一个是一次性比较一个是在滑动窗口里持续比较一个是把所有元素统一归组。从一道题延伸到一类题刷题效率会高很多。5.3 当数据规模变大单机哈希表还够用吗最后聊点工程化的思考。如果数据量非常大比如你有几千万个词条需要按异位词关系分组单机内存可能装不下这个哈希表。这时候的通用做法是分而治之先对每个字符串计算归一化键然后按键的哈希值分散到不同的分片上去处理每个分片内部再继续分组。键的设计完全复用只是把哈希表从单机挪到了分布式环境。更进一步的思路是在真实项目里你往往不需要精确分组只需要“相似”分组。比如搜索引擎的纠错和联想词它会把recieve和receive归到一类但不能硬用异位词关系因为字符构成并不完全相同。这种场景需要引入编辑距离、拼音归一化甚至向量化之后再聚类方法已经完全不同但那套“先计算标准特征再按特征归组”的骨架依然成立。说白了哈希表只是工具归一化键才是这道题藏在代码后面的思想。你能不能在面试中把这一层讲透往往比背出代码要重要得多。我自己对这道题的感受是它好就好在足够简单简单到你能看清一整类解题思想的脉络。每次有朋友问刷题该从哪起步我一般都会推荐把“字母异位词分组”和它的兄弟题一起刷了。代码写得再花哨不如把这个“投影-归组”的思维刻进脑子后面遇到再复杂的分组问题你至少不会慌。