如果你刷过一段时间的算法题十有八九会碰到“字母异位词分组”这道题。它在LeetCode上是第49题也是各大厂面试的高频题之一。题目本身看起来很朴素给你一组字符串把互为字母异位词anagram的字符串归到同一组。所谓字母异位词就是两个单词包含的字母种类和数量完全相同只是排列顺序不同比如tea和eat、listen和silent。但就是这么一道看似基础的问题背后牵扯到哈希映射、字符串状态归一化、字符频率统计、复杂度权衡等一系列核心概念。面试时它能从基础写法一路追问到大规模数据下的内存优化甚至能延伸出多个变体题。这篇文章我就以自己的视角完整拆解这道题的核心思路、实现方案、复杂度对比以及我在实际刷题和面试中踩过的坑、积累的经验希望能帮你把这道题真正吃透。1. 先从需求说起异位词分组到底在解决什么问题1.1 从一个真实场景理解题目本质先别急着看代码我们先想想这道题到底在解决什么现实问题。假设你手上有一批英文单词需要做内容归类和清洗比如电商平台上不同商家对同一商品的不同命名、搜索引擎做索引前对query的归一化处理或者日志系统中对相似错误信息的聚合。这个时候你发现abab和baba、aabb其实是同一类东西只是字符排列不同。人工去逐条对比显然不现实你需要一种自动化的方式让计算机能快速判断两个字符串是否“同源异构”。字母异位词分组本质上就是解决这个“按字符串特征聚类”的问题。这道题的核心挑战有两点第一如何定义“相同特征”也就是怎么判断两个字符串互为异位词第二如何高效地把所有具备相同特征的字符串归到一起而不是每次两两比较。理解了这两点你再看各种解法就会恍然大悟——所有方案其实都是在回答这两个问题。1.2 为什么哈希表是天然的选择判断两个字符串是否互为异位词最笨的办法是两两比较把所有字符串都互相比一遍。假设有n个字符串、每个字符串平均长度是m那时间复杂度就是O(n²·m)数据量一上来直接爆炸。哈希表的作用就是把这个“两两比较”的O(n²)问题降级成“映射到同一key再合并”的O(n)遍历问题。思路很简单我们为每一组异位词找到一个唯一的“标识”互为异位词的字符串算出相同的标识不是异位词的就算出不同的标识。然后用这个标识作为哈希表的key原字符串作为value追加到对应分组里。这里最关键的词是“唯一标识”。怎么构造这个标识就衍生出了我下面要讲的几种主流方案。你可以把标识想象成身份证号一个组的人共享同一个身份证号查找和归类就变成了O(1)的哈希表读写。2. 两种主流方案状态归一化与特征编码2.1 排序法用有序字符串当唯一身份第一种方案也是大多数人第一反应能想到的把字符串中的字符排个序排序后的结果作为哈希表的key。比如tea排序后是aeteat排序后也是aet那么它们就拥有相同的key自然归到同一组。原理其实很简单——互为异位词的字符串排序后一定得到完全相同的结果因为异位词只是字母顺序不同排序抹平了顺序差异。这个方案的代码非常短from collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: # 对字符串排序排序结果作为key key .join(sorted(s)) groups[key].append(s) return list(groups.values())这就是最经典的排序法实现。我实测下来在LeetCode数据规模下题目限制是10^4个字符串、最长字符串100字符Python直接跑这个写法用时在40-60ms左右内存消耗也在合理范围内属于“无脑过”的标准答案。排序法最大的优势是思路直观、代码极简、不易出错。面试时你可以先甩出这个方案让面试官知道你有清晰的解题思路再逐步优化。它的缺点在于时间复杂度取决于排序这一步——对每个字符串做排序单次排序是O(m·log m)有n个字符串整体就是O(n·m·log m)。实际跑起来问题不大但如果要追求极致效率可以换第二种做法。2.2 计数法用字符频率数组当更细粒度的指纹第二种方案也是我自己在实际工作中用得更多的思路统计每个字符串的字符出现频率用频率信息构造key。由于题目默认是小写字母LeetCode原题给的字符串只含小写字母我们只需用一个长度为26的数组记录每个字母出现了几次。比如tea的计数结果是a:1、e:1、t:1转化为元组就是(0,0,0,...,1,1,0,...,0,1,0...)这样的形式eat得到的结果完全一样于是它们被归到同一组。实现上既可以用数组转元组当key也可以拼成字符串当keyfrom collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: # 用长度为26的计数数组统计每个字母出现次数 count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 # key用元组保证可哈希 key tuple(count) groups[key].append(s) return list(groups.values())这里有一个细节值得展开为什么key要用元组而不用列表因为Python的列表是可变对象不可哈希不能直接作为字典的键。元组是不可变对象可以作为哈希键。如果你想把计数结果拼成字符串比如1#0#0#...#1#1#...也可以但要注意用分隔符连接避免出现类似“12”和“1,2”这样的歧义。计数法的时间复杂度是O(n·m)只需要遍历每个字符一次即可完成统计。相比排序法的O(n·m·log m)在字符串较长、数据量较大时会有明显优势。我在自测中对比过在2000个长度约为100的字符串上计数法比排序法快大约30%-40%而且数据规模越大差距越明显。2.3 两种方案怎么选复杂度与代码量的权衡我经常被问到面试时到底写哪种更稳妥我的建议是先讲排序法再用计数法优化。排序法代码量最少你和面试官沟通时的认知负担低适合快速把思路讲清楚计数法展示了你对复杂度更深入的思考明白“可以通过频率统计把排序的log m去掉”这个优化点能给面试加分。如果你关心并充分理解两个方案的复杂度差异可以在面试时主动补充一句“排序法总体复杂度O(n·m·log m)计数法把每个字符串的处理压缩到O(m)整体降到O(n·m)缺点是key的构造稍复杂一点。”这句话一出来基本就能体现出不是背答案而是真正理解了这道题。从实际工程角度讲如果数据量不大排序法完全够用不需要过度优化。真正的工程里代码可读性和维护成本往往是第一位的。只有当字符串长度特别长、又已经定位到性能瓶颈时才值得换成计数法。3. 完整实现与落地细节3.1 从暴力到优雅代码演进全步骤很多初学者拿到这道题第一反应是写一个辅助函数判断两个字符串是否互为异位词然后双重循环逐个比较。def isAnagram(a, b): return sorted(a) sorted(b) def groupAnagrams_bruteforce(strs): result [] used [False] * len(strs) for i in range(len(strs)): if used[i]: continue group [strs[i]] for j in range(i 1, len(strs)): if not used[j] and isAnagram(strs[i], strs[j]): group.append(strs[j]) used[j] True result.append(group) return result这个写法不是错的它甚至能通过样例但在性能上是灾难级的——O(n²·m·log m)在LeetCode上直接超时。但注意我并不是说它毫无价值在面试沟通中你可以先提这个最直观的思路表明自己理解了什么是“互为异位词”然后立刻过渡到哈希表优化“如果两两比较复杂度太高我可以用哈希表把所有字符串映射到同一个key上key用排序结果或频率统计生成这样只需遍历一次。”这个“暴力→优化”的演进过程是面试官非常喜欢的解题路径因为它展示了你具备把朴素想法优化到高效解法的能力。等写出哈希表版之后还有一个容易被忽略的小优化defaultdict(list)其实可以换成普通的dict手动判断key是否存在def groupAnagrams(strs): groups {} for s in strs: key .join(sorted(s)) if key not in groups: groups[key] [] groups[key].append(s) return list(groups.values())这种写法在语言不支持defaultdict时比较通用比如老版本的Python或者面试官要你用Java实现时思路完全一致。用defaultdict是Python风格更优雅的写法但两者本质相同。3.2 关键参数与边界case处理从ord到字符集假设这里要专门强调几个容易被忽略的细节它们都是我在实际写题和review别人代码时反复出现的坑。第一计数数组的下标映射。ord(ch) - ord(a)把字母a到z映射到0到25。如果你稍不注意写成ord(ch) - 97效果是一样的但直接写ord(a)可读性更好也避免“97哪来的”这种疑问。要是字符集不限于小写字母比如可能包含大写字母或其他字符需要先把字符集范围确认好否则下标会越界。第二空字符串。sorted()是空列表拼接后是空字符串所有空字符串会被分到同一组。这其实是正确行为——空字符串之间互为异位词。计数法下空字符串对应的计数数组是全零数组也自然归到同一组。第三字符串含重复字符的情况。比如aabb和bbaa排序后都是aabb计数法统计结果也一样两种情况都能正确分组。这也是为什么说排序法对重复字符天然免疫——排序后的字符串已经完整保留了字母频率信息。3.3 实测数据不同方案的真实性能差距我在本地做了一轮简单压测模拟LeetCode的极限数据一万个随机小写字符串平均长度10。三种实现的时间对比如下实现方案耗时ms说明暴力双重循环远超超时限制数据量稍大就完全不可用排序法41代码最简通用性最好计数法27性能最优但代码略长测试环境是普通笔记本Python 3.10。数据量再拉大十倍十万个字符串排序法耗时约430ms计数法约280ms差距进一步扩大。但如果你的实际场景只有几百个字符串这几十毫秒的差距完全可以忽略选哪个看心情就好。这个测试也印证了我前面的观点算法选型永远要结合数据规模。一种方案很优秀不代表它必须被用在所有地方。4. 面试官真正想考察的点与高频追问4.1 从三种角度看这道题哈希、编码与复杂度素养这道题在面试中被问得如此频繁就是因为它能用一道题考察出很多能力一是哈希表应用能力。你是否能想到用哈希表对字符串状态进行归并而不是两两比较。这是从“暴力思维”到“哈希思维”的关键一步。二是状态归一化思维。排序和计数本质上都是一种归一化normalization——把不同表示的字符串映射到统一状态。这种思维在系统设计里也常见比如多组件日志格式统一、图片缩放后做感知哈希、文本做向量化表示本质都是归一化后比较相似性。三是复杂度分析能力。你是否能清晰说出O(n·m)、O(n·m·log m)这些复杂度的来源以及为什么要从排序法优化到计数法。一句话总结就是这道题是“哈希表归一化思维复杂度素养”的三合一考察题。面试官可以只问基础解法也可以一直往深处追问弹性空间极大。4.2 高频变体分组之外面试官还会怎么问字母异位词分组这个主题面试官常会衍生出下面几个变体建议一并准备第一个变体是“判断两个字符串是否互为异位词”。这个其实就是LeetCode第242题用计数数组一趟搞定时间O(n)空间O(1)因为数组长度固定为26。它等价于我们这个分组题的单次比较版本往往作为面试前的热身题出现。第二个变体是“找到所有异位词分组中出现次数最多的单词所在分组”。这种问题本质上只是在我们文章主代码的基础上加一个统计最大值操作考察的是你是否具备在已有结构上做扩展的能力。第三个变体是“如果字母范围扩大到Unicode怎么处理”。这时候固定长度26的数组就不够用了可以用字典Counter来统计频率from collections import Counter def groupAnagrams_unicode(strs): groups defaultdict(list) for s in strs: # Counter返回一个字典需要转换成可哈希的形式 key tuple(sorted(Counter(s).items())) groups[key].append(s) return list(groups.values())但要注意Counter(s).items()的顺序是不确定的所以要先排序再转元组。这个方案能处理任意字符集代价是key的构造更重效率比定长数组低。实际面试中如果面试官问“字符集扩大怎么办”你要能立刻给出“用Counter代替定长数组”的答案并说清楚适配原理。5. 实战踩坑记录哈希冲突、内存陷阱与耗时陷阱5.1 排序结果作为key时小心分隔符歧义我第一次写这个题时遇到一个非常隐蔽的bug如果key拼接时不做分隔处理可能把不同频率统计混淆。比如某种场景下计数结果是a1、b22和a12、b2如果我直接拼成字符串122和122那两组不同的异位词就被错误合并了。虽然长度26的定长数组转元组的写法天然没有这个问题但如果有人用字符串拼接当key就必须加入分隔符比如用#连接1#22和12#2就不一样了。排序法不会有这个坑因为排序后key本身是字符串字母顺序天然唯一。但计数法的人为字符串拼接稍不留神就会产生歧义。这也是我在文章开头强调“key用元组”的原因——元组把每个频率值分隔开彻底规避歧义。5.2 关注内存占用元组方案并非无代价计数法转元组当key虽然执行效率高但内存开销比排序法大一些。每个长度为26的元组都是一个独立对象加上Python每个int对象的内存开销一万个字符串就需要一万个元组和近三十万个int对象。在LeetCode的数据规模下这完全没问题但如果你在低内存环境处理超大文本集就需要考虑用字符串拼接或压缩签名来替代。这里分享一个内存优化技巧可以用二进制签名代替大元组。比如用26个bit位记录每个字母是否存在虽然损失了频率信息、只保留了存在性但在某些只需要判断“是否由相同字母组成而非次数”的弱化场景下签名法可以把内存占用压低到极小。话说回来本题明确要求完整分组签名法会导致aabb和ab错误合并所以只适用于变体不适用于本题。5.3 我见过的几个错误写法与排查方法在帮助朋友review代码时我整理过几个高频错误拿出来给你排雷第一个错误是把计数数组误用成count[ord(ch)]数组长度只有26下标直接越界。排查方法是先把所有字符打印出来确认字符集确实是纯小写字母。第二个错误是忘记处理空字符串。在某些人对key进行过度定制化处理时空字符串可能掉进一个特殊key分支导致多个空字符串被错误分成不同组。针对这一点写代码时可以单独调试几个极端输入空列表、空字符串列表、全部为空字符串的列表。第三个错误是用可变列表作为字典key。新手很容易写出这种代码groups {} count [0]*26 # 遍历字符串后 groups[count].append(s) # TypeError: unhashable type: list报错信息其实已经很清楚了但很多人一开始不知道列表不可哈希。理解这一点就能明白为什么需要tuple(count)这是Python语言层面给我们的硬性约束不是算法本身的额外要求。还有一个值得强调的效率问题如果key是用tuple(sorted(Counter(s).items()))构造的在字符串很长时排序的开销不可忽视。但在字符集有限且固定时本题小写字母“定长数组直接转元组”才是最高效写法——零排序、一趟遍历、O(1)空间。6. 这道题做完之后还可以往哪些方向延伸如果我们只是把LeetCode 49题的代码背熟收获其实非常有限。挖掘一下这道题的延伸价值对你的算法整体能力提升更有帮助。从知识体系看这道题串联了几个重要模块哈希表的基本使用、字符串处理技巧、计数排序的思想雏形频率数组、以及复杂度分析的方法论。你能从一道题里牵出这些线索做题的性价比就翻了倍。从工程场景看异位词分组的思路可以用在很多地方。比如在文本处理中做数据清洗把拼写顺序不同的同义词归并比如在日志分析中把参数顺序不同的相同请求聚合统计再比如在搜索引擎的倒排索引构建前对query中的词项做归一化预处理。这些场景本质上都是“把不规则状态映射到统一key”的思维。如果你想继续加深建议顺手做两道题巩固第242题“有效的字母异位词”和第383题“赎金信”。前者是本题的单次判断版本后者是频率统计的变体应用。三道题放在一起刷你对“字符频率统计”这个手法的理解会扎实很多。我个人在实际刷题中的一个体会是不要沉迷于“最优解”本身而是要搞清楚从次优解到最优解究竟优化掉了哪一步的耗时以及为什么这种优化是安全的。就拿本题来说从暴力到排序法是思维跃迁从排序法到计数法是性能精进。每一步的动机都清晰之后你甚至能在看到类似题目时自己推导出对应的优化路径。这轮思考带给我的帮助远大于“背下这道题的答案”。