刷力扣hot100的朋友到第49题“字母异位词分组”这里通常会卡一下。这道题乍看很简单给你一组字符串把字母组成相同的分到一组。但真正动笔写的时候很多人的第一版代码要么超时要么分组逻辑有漏洞。而且这道题在面试里出现的频率极高不是因为它难而是因为它能一次性考察你对哈希表、字符串处理和算法复杂度的理解深度。这篇就把这道题从暴力思路到最优解、从代码到面试追问、从题目本身到工程场景全部拆开讲清楚。1. 这道题到底在考什么先看懂“异位词”的本质1.1 题目描述与输入输出的微妙之处先看原题。给定一个字符串数组要求将字母异位词组合在一起。所谓异位词就是组成字母相同、排列顺序不同的词比如eat、tea、ate这三个字符串就是一组典型的异位词。输入: [eat, tea, tan, ate, nat, bat] 输出: [ [ate, eat, tea], [nat, tan], [bat] ]注意输出结果里每组内部的顺序、组与组之间的顺序都不重要题目明确说了可以按任意顺序返回。这个“任意顺序”其实是个非常关键的提示它意味着题目并不要求保持原有的相对顺序解开了一个排序和哈希操作的枷锁。再注意一个细节输入是字符串数组字符串只包含小写字母。这个约束条件极其重要因为它直接决定了你能用什么方法做哈希键。如果字符范围扩大到大小写混用、数字、甚至Unicode字符解法就要做相应调整。很多人没注意到这一点在面试里被追问“如果包含大写字母怎么办”时当场愣住。1.2 核心认知异位词的本质特征是什么想要高效分组就要先想清楚一个问题两个字符串互为异位词它们之间有什么共同点字母构成相同出现的字符集合完全一样。每个字符出现次数相同这比集合相同更严格aab和ab虽然字母集合都是{a, b}但显然不是异位词。字母排序后的结果必然相同将两个异位词各自排序会得到完全相同的字符串。这三个特征并不是并列关系而是从外到内层层深入的。如果用生活化的类比来理解每个字符串就像一盒积木异位词就是那些“积木颜色和数量都相同、只是摆放顺序不同”的拼搭成品。你要做的就是把这些看似不同、实际用同一套积木搭出来的成品归到同一个抽屉里。有了这个认知解法思路就自然浮出水面了我们需要一个“归一化函数”把任意字符串映射成一个唯一的“指纹”异位词之间指纹必须相同非异位词之间指纹必须不同。然后借助哈希表按照指纹分组以O(1)的平均复杂度完成归类。整个题目的难点全集中在这个“指纹”怎么设计上。2. 解法一排序字符串作为指纹大多数人的第一直觉2.1 思路推导为什么排序能够区分异位词最直观的想法是既然两个异位词排序后完全相同那就把排序后的字符串作为哈希表的键。对eat排序得到aet对tea排序也得到aet这两个字符串自动落到同一个键下。对bat排序得到abt跟前面的键不同就自动分到另一组。这种做法的漂亮之处在于它把“字母构成和数量相同”这个复杂条件化简成了“排序后字符串相等”这个简单条件。因为任何排序算法只要两个字符串的字符多集相同排序结果必然相等反之如果排序结果相等字符多集也必然相同。这是一个双向等价的判断。2.2 代码实现与复杂度分析from collections import defaultdict def groupAnagrams(strs): mp defaultdict(list) for s in strs: key .join(sorted(s)) mp[key].append(s) return list(mp.values())代码非常短核心逻辑就三行对每个字符串排序把排序结果当键把原字符串存进对应列表。时间复杂度怎么算假设输入有n个字符串每个字符串平均长度为k。对每个字符串排序的时间是O(k log k)一共有n个字符串所以总时间是O(n * k log k)。空间复杂度是O(n * k)因为哈希表里要存所有的原字符串。collections.defaultdict这个数据结构非常方便避免了手动判断key是否存在的繁琐逻辑。用普通字典需要这样写def groupAnagrams(strs): mp {} for s in strs: key .join(sorted(s)) if key not in mp: mp[key] [] mp[key].append(s) return list(mp.values())两种写法等价但defaultdict明显更简洁。如果你面试用的是Java也有类似的computeIfAbsent方法MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key String.valueOf(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values());2.3 这个解法的边界在哪里排序法虽然直观但是有一个隐患如果字符串长度k很大排序开销O(k log k)会迅速膨胀。假设一个字符串有十万个字符对每一个都做一次全量排序这显然不是最优方案。另外还有一个容易忽略的细节Python的sorted(s)返回的是字符列表必须用.join()拼接回字符串才能作为哈希键。如果你直接拿列表当键Python会报TypeError: unhashable type: list。这个报错很多新手都遇到过其实理解了列表是可变对象、不能哈希就知道为什么不能当键了。那么问题来了有没有办法绕开排序把时间复杂度进一步压到O(n * k)有就是下面的计数法。3. 解法二字符计数序列作为指纹在时间上做到极致3.1 思路推导用每个字母出现的次数构造唯一键题目约束了输入只包含小写字母这意味着总共只有26种可能字符。我们可以为每个字符串统计每个字母出现的次数得到一个长度为26的计数数组把这个数组作为哈希键。两个字符串互为异位词当且仅当它们每个字母的出现次数完全相同。这个判断比排序法更直接也避开了排序的O(k log k)开销。统计字母频率只需要遍历一次字符串时间复杂度是O(k)。但这里有一个关键的技术细节长度为26的列表list不能直接作为哈希键因为列表是可变的、不可哈希的。有几种处理方案转成元组tuple(count)元组不可变可以作为键。转成带分隔符的字符串把每个数字用#连接成一个字符串比如1#2#0#0#...。编码成字符串将次数映射成字符或用ASCII编码技巧。方案1最简洁方案2更省内存。推荐在面试中优先写方案1代码可读性最好。3.2 代码实现元组版本与字符串版本from collections import defaultdict def groupAnagrams(strs): mp defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 key tuple(count) mp[key].append(s) return list(mp.values())内部循环里ord(ch) - ord(a)把字母映射到0到25的索引。比如字符c的ASCII码是99a的ASCII码是97相减得2对应计数数组的第三个位置。字符串版本可以这样写def groupAnagrams(strs): mp defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 key #.join(str(x) for x in count) mp[key].append(s) return list(mp.values())如果不想用str(x)一个一个转换也可以用bytes的方式构造更紧凑的键key .join(chr(ord(a) x) for x in count)不过这个写法依赖字符编码不建议在面试里用容易把自己绕晕除非你很清楚ASCII码的边界在哪。3.3 两种核心解法的横向对比对比维度排序法计数法时间复杂度O(n * k log k)O(n * k)空间复杂度O(n * k)O(n * k)代码复杂度极简略长需要构造键键的可读性可读性好如aet元组太长不可直观理解是否依赖字符范围不依赖任何字符都能排序依赖需要预先知道字符范围对超长字符串的性能差优两者在绝大多数情况下都能通过力扣的测试但如果你在面试中先说出排序法再主动提出计数法的优化面试官的好感度会明显不同。这体现的不只是你会写代码而是你能比较不同方案的优劣。4. 容易被忽略的边界条件、面试追问与进阶陷阱4.1 边界情况逐一排查这道题看起来简单但边界情况并不少。我梳理了几个容易踩的坑空数组输入[]输出应该是[]。两种解法都能自然处理因为循环根本不执行。只有一个空字符串输入[]输出应该是[[]]。空字符串排序后还是空字符串计数数组全是0也能正确分组。只有一个字符的字符串输入[a]排序法键是a计数法键是(1,0,0,...,0)都能正确工作。大量重复字符串比如一万个eat所有解法都退化成把同一个键追加一万次这里defaultdict的追加操作是O(1)的没有性能问题。所有字符串都是异位词输入[abc,bca,cab]哈希表里只有一个键输出是一个包含所有字符串的列表。4.2 面试官最常问的三个延伸问题第一个问题“只包含小写字母”这个约束去掉字符串可能包含大写字母、数字、空格怎么办两种方案。如果字符集仍然有限比如ASCII范围内的128个字符计数数组就开128位用ord(ch)直接作为索引。如果字符集不确定比如可能是Unicode排序法更保险因为它不依赖字符范围。简洁的回答是计数法需要关心字符集大小排序法天然通用。第二个问题能不能不用排序也不用计数数组用质数乘积作为键可以。给26个字母分别分配一个质数如a2, b3, c5, d7, e11, ...把字符串中每个字母对应的质数相乘得到的结果就是唯一的指纹。因为质数分解的唯一性保证了这个乘积能唯一确定每个字母的出现次数。这个思路非常巧妙但有一个致命问题整型溢出。即使是用Python的任意精度整数当字符串很长时乘积会变成天文数字计算和比较的速度都会急剧下降。用Java的int或long更是直接溢出需要用BigInteger来处理。所以这个方案理论上最优工程上最多作为思路亮点展示。第三个问题如果要求每一组内部按字典序排序怎么改分组逻辑不变只是在返回之前对每组内部做排序result [sorted(group) for group in mp.values()]注意排序的是组内字符串不是分组键。这里要厘清排序的对象否则容易把思路搞混。4.3 从力扣的判题机制看代码的性能优化力扣上这道题有的提交里会看到类似这样的写法class Solution: def groupAnagrams(self, strs): ans {} for s in strs: key tuple(sorted(s)) ans.setdefault(key, []).append(s) return list(ans.values())注意tuple(sorted(s))这个写法把排序后的字符列表转成元组利用元组的不可变性直接作为键省去了join的过程。在Python里对小字符串来说这种写法有时比计数法更快因为join一个长度为k的字符串其实也需要遍历k个字符而转元组也是遍历k个字符两者开销接近但tuple(sorted(s))写起来更短。这个细节告诉初学者分析复杂度是理论层面实际运行速度还受常数因子影响。另外力扣判题时会用一些极端用例例如大量长度相同但互不为异位词的随机字符串。这种情况下哈希碰撞会增多但Python字典对字符串键的哈希处理得很好总体影响不大。5. 从异位词分组发散出去的算法题与通用思路5.1 姐妹题找到字符串中所有字母异位词力扣第438题“找到字符串中所有字母异位词”可以说是49题的直接变体。题目要求在一个长字符串s中找到所有p的异位词的起始索引比如s cbaebabacd、p abc输出[0, 6]。这道题如果套用49题的思路会很自然地想到枚举所有长度为len(p)的子串判断它和p是否互为异位词。但这种做法的复杂度是O(n * k * log k)太慢了。更优的方案是滑动窗口 字符计数from collections import Counter def findAnagrams(s, p): ns, np len(s), len(p) if ns np: return [] p_count Counter(p) s_count Counter() res [] for i in range(ns): s_count[s[i]] 1 if i np: if s_count[s[i - np]] 1: del s_count[s[i - np]] else: s_count[s[i - np]] - 1 if s_count p_count: res.append(i - np 1) return res核心思想是维护一个长度恒为len(p)的窗口随着窗口右移只更新进入和离开的字符这样每个字符只被处理一次总复杂度O(n)。这个思路和49题计数法的指纹思想一脉相承窗口内字符计数数组与目标计数数组是否相等等于在动态地比较“指纹”。5.2 另一类变体异位词的最小分组数有的公司在笔试中会把49题扩展成这样给定两个字符串数组要求找出它们“配对”的异位词组数或者要求把若干字符串划分为最少数量的组每组内任意两个字符串都是异位词。这类问题本质不变还是分组指纹的问题。只需要把“组”的条件从“两两互为异位词”翻译成“指纹相同”前面的哈希表方案就能直接迁移。少数情况下会要求你按组的大小排序输出那就对mp.values()按长度排序即可。5.3 引申工程中的指纹与分组思维这道题的方法论并不仅仅属于力扣。在实际工作中“把复杂对象归一化成指纹再按指纹分组”这个套路几乎无处不在日志聚类对大量日志文本做归一化把变量部分替换成占位符然后按归一化后的模板分组快速分析故障类型。数据去重对文档内容计算哈希哈希相同的判定为重复内容适用于爬虫去重、缓存去重。同义词扩展搜索引擎会对查询词做归一化处理字母异位词在拼写纠错场景中就是一类典型。如果你想往工程方向再延伸一步可以把排序法中的“归一化函数”抽象成接口比如Java里用FunctionString, String表示Python里直接定义成函数参数def group_by_key(strs, key_func): mp defaultdict(list) for s in strs: mp[key_func(s)].append(s) return list(mp.values()) # 排序法 group_by_key(strs, lambda s: .join(sorted(s))) # 计数法 group_by_key(strs, lambda s: tuple(Counter(s)[ch] for ch in abcdefghijklmnopqrstuvwxyz))这种抽象让代码的复用性更高也更能体现你对“分组语义”的理解。6. 哈希键设计中的工程智慧从这题看透力扣考察的本质6.1 为什么说这道题考察的不是算法而是设计很多人把49题归类为“哈希表”题就完了但这个归类太粗糙。哈希表在这道题里只是一个容器真正决定解法优劣的是哈希键的设计。你可以用排序后的字符串、计数元组、质数乘积甚至ASCII编码后的字节数组作为键每一种设计都有不同的时间、空间和表达能力。这种“设计键”的能力恰恰是数据结构考试中很少教、但工程中极其重要的能力。比如在Redis里为每个用户维护一个状态集合你要设计一个能唯一标识用户状态的key在数据库分表中你要选定一个分布均匀的分表键在分布式缓存里你要确定什么数据放到同一个分片里。这些场景全是“键设计”问题。所以面试官问这道题表面看你写代码实际在考察三件事一是能不能把字符串转换成一个可比较、可哈希的等价形式。很多人欠缺的就是这一步抽象直接暴力两两比较写出了O(n² * k)的代码。二是分析复杂度的能力。同样是哈希表分组排序法O(n * k log k)和计数法O(n * k)的差别你能不能脱口而出三是对语言特性的熟悉程度。Python里元组和列表的哈希差异、defaultdict的用法、ord和chr的映射这些都是细节但细节决定代码是否优雅。6.2 如果你在面试中遇到这道题建议这样回答第一步先确认输入规模、字符范围。问清楚“字符串只包含小写字母吗”这既是澄清需求也给自己后面的计数法铺路。第二步先说一个最直观的解法排序法并估算复杂度展示你具备从简单方案入手的工程思维。第三步主动提出优化方案计数法说明为什么能省掉log k因子以及键的具体构造方式。第四步如果面试官感兴趣再补充质数乘积的思路和它的溢出隐患展示你的知识深度。这一步一步下去绝对不再只是“做过这道题”而是“理解这道题”。6.3 关于刷题顺序的一点体会很多刚开始刷hot100的朋友会从第1题开始按顺序来但我的建议是把49题这类“考察核心数据结构、但不涉及复杂算法”的题目放在早期是合理的它能帮你建立哈希表的直觉。真正忌讳的是只刷题不复盘。像这道题如果你把排序法和计数法都跑通把面试官可能的追问都提前想过一遍那么以后遇到“最长连续序列”“两数之和”这类哈希题你会下意识地去想键应该怎么设计、碰撞怎么处理、能否转换成更简单的等价形式。这种“下意识”才是刷题最大的收获。