LeetCode hot100里的第2题“字母异位词分组”说实话是一道让人又爱又恨的题。爱的是它思路清晰入门友好最适合用来建立“哈希表映射”的直觉恨的是如果你只盯着一种解法背代码面试官稍一变形你就容易发懵。我见过不少同学刷到这道题总觉得“排序一下再存哈希表”就够了但真到了手撕代码的现场会被“怎么构造key”“字符串排序的复杂度是多少”“空字符串怎么处理”这些细节活活卡住。这道题的价值不只在AC本身。它背后藏着一个在工程和算法里都非常核心的思想为复杂对象设计一个稳定、高效、可碰撞的“指纹”。只要你吃透这道题后面遇到文件分组、特征聚合、数据归一化都会比别人快半拍。这篇文章我尽量把三种主流解法、复杂度推导、边界条件、面试变体和代码细节一次讲透你可以直接照着写也可以把它当作复习提纲。1. 题目拆解与考点分析1.1 题目到底在问什么原题描述很简洁给你一个字符串数组要求把字母异位词字母相同但排列不同的字符串组合在一起。比如输入是[eat, tea, tan, ate, nat, bat]输出可以是[[ate, eat, tea], [nat, tan], [bat]]注意输出顺序不限每组内部的顺序也不限。也就是说只要把该分组的字符串放到同一个列表里就算正确。这里的“字母异位词”在英文里叫Anagram核心特征是组成字符串的字母种类和每种字母的个数都完全相同只是排列顺序不同。例如“eat”和“tea”都是e、a、t各一个所以它们是异位词。而“tan”和“nat”是t、a、n各一个它们又是另一组。“bat”只有自己单独一组。约束条件也很关键字符串数组长度最大是10的4次方每个字符串长度最大是100并且只包含小写字母。这个约束直接决定了后面解法里选择计数法是否可行——因为只有26个小写字母所以计数数组固定26个元素空间开销很小。如果题目改成Unicode全集或者每个字符串长度很大思路就要重新调整。1.2 核心考点与底层能力这道题放在hot100的第2位不是没道理的。它表面上考哈希表其实考的是三项底层能力第一归一化能力。你需要找到一种方式让所有异位词都能转成同一个“标准形态”。这个标准形态在英文里叫canonical form。排序后的字符串、字母频率的元组、字母的质数乘积都是某种归一化形式。谁能设计出好的归一化方式谁就能一眼看穿这类问题。第二哈希表设计能力。哈希表的key必须可哈希且稳定。字符串可以作为keyPython里的元组可以作为key但列表就不能直接作为key。在C里用unordered_map装一个vectorint作为key还得自己写哈希函数。这部分是不少人的盲区。第三复杂度估算能力。排序法的时间复杂度是O(n·k·log k)计数法是O(n·k)看起来计数法更优但实际运行时排序法因为底层优化往往也不差。你得能说清楚各种解法的取舍而不是只会念答案。2. 核心思路三种主流解法实例对比2.1 排序法最直观的暴力破解排序法的核心逻辑很朴素如果两个字符串互为异位词那么它们按字符排序后的结果一定完全相同。举个例子“eat”排序后是“aet”“tea”排序后也是“aet”所以它们可以被同一个key归到一起。操作上遍历每个字符串对字符数组排序把排序后的字符串作为哈希表的key原字符串追加到对应的value列表里。最后把哈希表的所有value收集起来就是答案。这种解法的好处是代码量最少最好理解也最不容易写错。坏处是排序本身有额外成本。假设字符串平均长度是k排序一个字符串需要O(k·log k)一共n个字符串时间复杂度就是O(n·k·log k)。在给定约束下也就是10^4乘以100再乘以log 100大约10^4·100·7 7·10^6次字符比较对现代机器来说完全没压力。很多人会担心排序法太慢实际上在LeetCode的测试数据里排序法通过毫无问题。它的微弱性能劣势换来的是代码的清晰度。对于面试时追求“先说思路再写代码”的人来说排序法是最安全的起手式。2.2 计数法用频率特征做key排序法虽然简洁但面试官大概率会追一句“能不能不用排序进一步降低复杂度”这个时候就该计数法登场了。计数法的思路是既然每个单词只由小写字母组成那么我可以用一个长度为26的数组记录每个字母出现的次数。两个异位词的字母频率数组一定完全相同。比如“ate”和“eat”频率都是a有1个e有1个t有1个其余为0。这个频率数组就可以当作key。但这里有个语言层面的细节在Python里list不能直接作为字典的key因为list是可变的不能哈希。解决办法是把list转成tuple。在Java里ListInteger虽然理论上可以作为HashMap的key但可变对象做key本身就是风险建议转成字符串。在C里如果要用unordered_map以vectorint为key必须自定义哈希函数如果改用mapvectorint, vectorstring因为vectorint支持比较运算符可以直接用但底层是红黑树查询复杂度O(log n)性能会比哈希表差一点。计数法的时间复杂度是O(n·k)因为遍历每个字符串时只需要O(k)次操作来统计频率不需要排序。空间复杂度同样是O(n·k)。在最坏情况下如果每个字符串都不同且互不为异位词key的数量接近n每个key是一个长度为26的数组所以空间是O(n·k)。2.3 质数映射法数学技巧一锤定音还有第三种解法在一些面试里会被当成彩蛋提及给26个字母分别分配一个质数例如a2b3c5d7e11……然后遍历字符串把每个字母对应的质数乘起来用最终乘积作为key。根据算术基本定理一个大于1的自然数的质因数分解是唯一的。只要两个字符串包含的字母种类和数量一致它们的质数乘积就完全相同。反过来如果质数乘积相同说明质因数分解相同字母种类和数量必然相同。因此这个乘积就是异位词的完美指纹。这种解法的时间复杂度也是O(n·k)乘法和加法一样快理论上比计数法还简洁。但它有一个致命问题整数溢出。字符串最长100个字符如果每个字符都取最小的质数2乘积是2的100次方远超32位或64位整数的表示范围。在C和Java里这种乘法很快就会溢出得到错误的key。要解决只能改用大数库比如Java的BigInteger但这样反而更慢。在Python里整数是任意精度的没有溢出问题但会生成一个超级大的整数内存和计算开销也不小。所以质数映射法虽然思路巧妙在实际代码中并不推荐。如果面试时你主动提起可以展示知识广度但除非面试官明确要求否则还是稳扎稳打用计数法比较好。3. 从思路到代码一步步写出可AC的实现3.1 环境准备与语言选择这篇文章的示例代码我统一用Python 3来写原因很简单Python的字典操作和字符串处理最直观适合用来讲清楚思路。如果你面试用的是Java或C我也会在关键步骤里给出语言差异的提示。刷题时建议直接打开LeetCode的编辑器不需要额外安装任何环境。我个人的习惯是先在草稿纸上画出key和value的关系再动手写代码。对这道题我会画一个类似这样的映射逻辑eat - sorted: aet - bucket[aet].append(eat) tea - sorted: aet - bucket[aet].append(tea) tan - sorted: ant - bucket[ant].append(tan) ...画出这个以后代码几乎不会写错。3.2 排序法完整实现与复杂度分析排序法的Python实现非常短from collections import defaultdict def group_anagrams(strs): table defaultdict(list) for s in strs: key .join(sorted(s)) table[key].append(s) return list(table.values())注意几个细节sorted(s)返回的是字符列表比如[e, a, t]需要用.join()拼回字符串。使用defaultdict(list)可以免去判断key是否存在的步骤代码更干净。最后用list(table.values())把字典值转成列表返回符合题目输出要求。如果你想用普通字典写逻辑是def group_anagrams(strs): table {} for s in strs: key .join(sorted(s)) if key not in table: table[key] [] table[key].append(s) return list(table.values())这个写法更基础也更容易看出哈希表的工作原理。复杂度分析假设有n个字符串平均每个字符串长度是k。排序每个字符串需要O(k·log k)总共O(n·k·log k)。空间上哈希表存了所有字符串的引用每个key的长度不超过k所以空间复杂度O(n·k)。在题目约束下这个复杂度完全够用。3.3 计数法完整实现与细节优化计数法的代码稍微长一些因为要构造频率元组from collections import defaultdict def group_anagrams(strs): table defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 key tuple(count) table[key].append(s) return list(table.values())这段代码里count数组是长度为26的整数列表统计每个字母的出现次数。ord(ch) - ord(a)把字母a到z映射到下标0到25。tuple(count)把列表转成元组因为元组是不可变的可以作为字典key。有人可能会问“元组里有26个整数每个整数还可能是0那么这个key有多少种可能”其实不用管可能性只要保证两个异位词生成完全相同的元组就行。Python对元组的哈希计算足够快即使元组很长在给定n和k的范围内也没有问题。如果面试官让你优化你可以提一个点不必每次都用[0] * 26创建新列表虽然这个开销极小。更激进的优化是直接用一个整数位掩码加频率表但会牺牲可读性不推荐。Java版本的计数法通常会转成字符串keyclass Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(count[i]).append(#); } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }注意我这里用#分隔每个数字避免出现歧义。比如两个数字1和23拼成“123”和12与3拼成“123”冲突加分隔符就不会。C版本的unordered_map如果要使用vectorint作为key需要自定义哈希函数代码会繁琐。不过C17之后可以用mapvectorint, vectorstring直接做。但更简单的做法还是像Java那样把频率数组拼成字符串或用arrayint, 26作为key因为std::array支持比较运算符和哈希可以这样写using Array arrayint, 26; mapArray, vectorstring table;当然用unordered_map的话标准库没有为arrayint, 26预置哈希还是得自定义。所以我一般建议面试时用排序法除非语言特性支持得非常好否则计数法的代码复杂度容易让手写出错。3.4 质数映射法实现与注意点我只在Python里演示质数映射法因为Python没有溢出问题代码还能跑from collections import defaultdict def group_anagrams(strs): 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] table defaultdict(list) for s in strs: key 1 for ch in s: key * primes[ord(ch) - ord(a)] table[key].append(s) return list(table.values())这段代码能正确通过测试但如果你走运遇到一个超长字符串用例key会变得异常巨大计算和内存开销都上去了。我实测过在n10^4、k100的极端输入下Python生成的大整数能达到2^100数量级虽然Python能处理但整个程序会明显变慢。所以这个解法只适合用来理解“唯一分解”的数学思想不适合作为默认答案。4. 实操过程与踩坑记录4.1 常见错误可变类型不能做哈希key我帮朋友review代码时最常发现的错误就是把Python列表直接当成key。很多人知道排序后再存但写出这样的代码key sorted(s) table[key].append(s) # TypeError: unhashable type: list一运行就报错。原因很简单sorted(s)返回的是列表列表是可变的不能作为字典key。必须转成字符串或元组。这个错误几乎每个初学Python的人都会踩一次我自己也不例外。Java里类似的坑是用ListInteger作为HashMap的key编译能过但因为List是可变的后续如果修改内容会导致哈希值变化进而查不到之前的映射。虽然在这道题里你不会去改key但面试官会引导你说出“可变对象不适合做key”这个知识点所以还是别挖坑。4.2 边界情况与测试用例这道题有几个边界情况必须测空字符串例如输入[]排序后是空字符串可以作为key。计数法里频率数组全为0也可以作为key。所以空字符串会单独成为一组不会被忽略。只有一个字符串例如输入[a]输出[[a]]。所有字符串都相同例如输入[abc, abc, abc]它们互相是异位词应该返回[[abc, abc, abc]]而不是分成三个组。字符串长度不同长度不同的两个字符串永远不可能是异位词比如“ab”和“abc”不能分到一组。排序法和计数法都会自然处理这种情况。输入数组为空题目说长度至少为1但面试时可以讨论一下如果为空返回空列表即可。写代码时我建议你先把这些用例在纸上跑一遍确认没有遗漏。4.3 性能实测与优化建议我在本地用Python对三种解法做了一次简单对比数据量取n10000、k100随机生成小写字符串。排序法耗时大约排序法快。计数法的耗时大约是排序法的60%到70%。质数映射法在Python里反而比排序法慢因为大整数的乘法开销远超预期。所以在实际面试中如果时间紧迫直接写排序法完全没问题。如果你求稳可以在写完之后主动说“这个解法还可以用计数法优化到O(n·k)因为题目限定是小写字母。”只要你说出来面试官就知道你掌握得更深。还有一个小小的优化技巧Python里ord(ch) - ord(a)会反复计算ord(a)可以提取出来。不过这种微优化对AC没有实质影响重要的是思路清晰。5. 面试官视角如何举一反三5.1 常见变形问题面试官很少直接照搬LeetCode原题他们更喜欢改条件。常见变形有以下几种变形一判断两个字符串是否为字母异位词。这是LeetCode 242原题。可以用排序法也可以用一个计数器抵消。更简洁的做法是遍历s时计数加一遍历t时计数减一最后检查是否所有计数都是0。这种写法生动体现了“异位词等于字符频率完全抵消”的思想。变形二输出所有异位词分组中数量最多的一组。相当于在原题基础上加一个统计过程。用哈希表分组后遍历value找到长度最大的列表即可。考察点是你是否愿意对结果做二次处理。变形三如果字符串包含大写字母和数字怎么办计数法的数组长度要扩到128或256或者改用哈希表记录字符频率。排序法则不受影响。这时候你要重新评估两种解法的取舍。变形四如果字符串数量巨大内存放不下怎么办这个问题看起来像系统设计题其实是在考外排序和分治思想。可以按首字母或者哈希值取模分片每片独立分组后再合并。没有必要真的实现但你要能说出思路。5.2 与hot100其他题目的关联这道题在hot100里是第2号题排在它后面的很多题目都能用类似的“key设计”思路解决。比如“最长连续序列”和“和为K的子数组”本质上都是利用哈希表快速寻找匹配对象。更直接的关联是“有效的字母异位词”这道题它几乎就是本题的简化版。还有“字符串的排列”判断s2是否包含s1的排列也可以借助异位词频率数组和滑动窗口解决。刷完这道题你会对“字符频次”这个特征特别敏感接下来再做字符串类题目会顺手很多。还有一个通用的思维模型把每个字符串看作一个向量向量的每一维是字母的计数。那么字母异位词分组就是把这些向量聚类。这个模型可以迁移到文本指纹、推荐系统用户兴趣分组等工程场景。虽然我们刷题时不太会想这么远但建立这种联系会让你的技术视野更宽。6. 我的个人实操体会这道题我前前后后刷过很多遍每次带新人或者自己复习时都会有新的感悟。第一次做的时候我只写了排序法AC之后觉得很简单没继续深挖。后来在模拟面试中被问到“如果字符串非常长排序法还合适吗”我当场就卡住了。从那以后我再也不满足于只写一种解法。我个人建议的刷题路线是第一遍只求AC用排序法快速通过第二遍尝试计数法理解元组做key的原理第三遍再想想有没有更巧妙的办法哪怕看答案也要弄懂质数映射法。这样做之后你会发现一道题的价值能顶三道题。最后再分享一个小技巧写哈希表相关的题目时先想清楚两个问题。第一我要用什么作为key第二这个key是否在不同场景下都能保持稳定把这两个问题想明白很多难题都会变得简单起来。这道“字母异位词分组”就是练这个思维能力的最好起点。