LeetCode 热门 100 题里第 49 题“字母异位词分组”属于那种一眼看去人畜无害、真动手全是细节的经典题。我第一次刷它的时候觉得这不就是字符串排序套个哈希表吗后来在面试实战和帮别人复盘代码时才发现这道题关于哈希 key 的设计、复杂度的推导、边界条件的处理能写出来的内容远比题目本身长。这篇文章会从题目理解开始把排序法和计数法两种主流解法一步步拆开再附上我实际踩过的坑和排查记录适合正在准备面试、刚刷到“哈希表”专题的朋友。看完你能独立手撕这道题也能应付面试官随后的追问。1. 这题到底在问什么先别急着写代码1.1 什么是字母异位词题目给了一堆字符串要求把“字母异位词”分到同一组。字母异位词的定义是由相同数量、相同种类的字母组成只是排列顺序不同。比如“eat”和“tea”“tan”和“nat”每组里的词打乱字母顺序后就是同一个词。举个例子strs [eat, tea, tan, ate, nat, bat]正确输出可以是[[bat], [nat, tan], [ate, eat, tea]]组与组的顺序无所谓组内顺序也无所谓只要是这些集合就行。也就是说题目并没有要求你把组内再按字典序排列也没有要求组之间按某种顺序输出这一点在很多人的代码里被过度实现——多写排序纯属浪费。判断两个单词是否异位词最朴素的办法是逐个比较字母数量或者把两个词排序后比较。单看两个词似乎很容易但题目输入最多有 10^4 个字符串每个字符串最长 100 个字符两两比较肯定不行。所以核心就是能不能找一个“归一化”的方法让同一组的词都映射到同一个标识上再用哈希表聚合。1.2 题目边界和隐含条件LeetCode 官方题解里明确写了输入约束strs.length 在 1 到 10^4 之间strs[i].length 在 0 到 100 之间且 strs[i] 仅包含小写字母。但这是“当前版本”的约束面试官完全可能改条件比如加上大写字母、数字甚至中文。我为什么要专门提约束因为解法是跟着约束走的。约束只有小写字母计数法才能固定开一个长度为 26 的数组如果字符范围变大数组长度就要跟着变或者换一种 key 设计。这道题表面上考哈希表实际上考的是“不变量”的提取你需要找到一种表示方式让相同字母组合的词拥有完全相同的 key让不同字母组合的词尽可能不撞 key。还有一个容易被忽略的边界字符串为空。空字符串没有任何字母它的排序结果是空串计数数组是全 0。无论哪种解法都要保证空字符串能被单独分到一组而不是变成特殊值导致程序崩溃。我见过有人直接在函数开头写if s is None把空串过滤掉了导致结果丢失这就是读题不仔细。2. 排序法最直觉的做法也是面试的及格线2.1 排序法为什么能成立排序法基于一个非常直观的观察两个字符串互为异位词当且仅当它们排序后的结果完全相同。“eat”排序是“aet”“tea”排序也是“aet”“ate”排序还是“aet”“bat”排序是“abt”和其他词都不一样。所以算法骨架就是三句话遍历所有字符串对当前字符串排序得到 key把原字符串塞进哈希表[key]对应的列表里。最后把哈希表的所有 value 收集起来就是答案。这个方案为什么是面试的及格线因为它简单、正确、容易解释几乎不会写错。哪怕面试官后面要求优化你也已经证明了“我能快速给出一个可行方案”。我面试别人的时候最怕的不是候选人给出排序法而是候选人连排序法都说不清楚直接上计数法然后卡在 key 拼接上。2.2 代码实现与复杂度Python 写法最简洁因为 sorted 可以直接作用于字符串返回字符列表再 join 回字符串就行def groupAnagrams(strs): from collections import defaultdict lookup defaultdict(list) for s in strs: key .join(sorted(s)) lookup[key].append(s) return list(lookup.values())这里用defaultdict(list)比普通 dict 方便得多遇到新 key 时自动初始化一个空列表省掉了if key not in lookup: lookup[key] []这行判断。如果你用普通 dict一定要记得手动处理键不存在的情况否则会抛 KeyError。Java 需要先把字符串转成 char 数组排序再转回 Stringpublic ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }C 里直接对字符串排序就行因为 std::string 支持原地排序class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (string s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring ans; for (auto [k, v] : mp) ans.push_back(v); return ans; } };三个语言的做法本质一样唯一的区别只是语言 API。复杂度也很有必要说清楚假设输入有 n 个字符串每个字符串平均长度是 k那么每个字符串排序需要 O(k log k)总时间复杂度就是 O(n × k log k)。空间上哈希表存的是所有原始字符串差不多是 O(n × k)。这里有个很多人忽略的点如果字符串数量很大、但每个字符串很短排序法的 log k 部分其实可以忽略不计性能完全够用。这也是我在实际面试中推荐“先写排序法”的原因——大多数输入场景下它已经能 AC 了没必要一上来就炫耀计数法。3. 计数法进阶解法理解 key 的设计是关键3.1 计数数组怎么当 key面试官紧接着大概率会问“能不能把复杂度里的 log k 去掉”这时候就要引出计数法。既然互为异位词的单词拥有完全相同的字母计数那我们就不排序直接统计每个字母出现次数得到一个长度 26 的数组。比如“eat”的计数是[1, 0, 0, 0, 1, 0, ..., 1]a 出现 1 次e 出现 1 次t 出现 1 次tea 的计数完全一样。数组天然适合做“归一化表示”。问题来了数组本身不是哈希表的合法 key。Python 里 list 不可哈希Java 里数组的 equals 是引用比较直接用数组当 key 会出事。所以需要把计数数组序列化成一个可以哈希、且不会歧义的字符串。这里就涉及一个经典坑序列化格式。如果你直接不加分隔符地把数字拼在一起比如把[1, 0]拼成10把[10, 1]也拼成101两者就撞了。虽然原题限制字符串长度最大 100理论上字母计数最多 100数字长度最多 3 位但数字间没有分隔符时是会产生歧义的。所以常见做法是加一个分隔符比如1#0#0#...#1或者显式给每个数字固定宽度补零到 3 位001#000#000#...。我在实际测试中发现补零的方式更费空间但完全无歧义加分隔符的方式直观、可读性强两者都可以。更优雅一点在 Python 里也可以直接用tuple(count)作为 key因为元组可哈希而且不需要拼字符串。3.2 实现与分隔符的坑用计数法实现时我建议先明确 key 的设计再写主循环。下面是一段 Python 实现def groupAnagrams(strs): from collections import defaultdict lookup 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) lookup[key].append(s) return list(lookup.values())这段代码的 key 是1#1#0#0#...#1这样的字符串。每次统计完一组计数就把它拼成 key然后塞进哈希表。Java 版本同样要用 StringBuilder 拼 26 个数字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()); }如果你希望在 Python 里避开字符串拼接的开销可以直接用tuple(count)作为 key因为 tuple 是天然可哈希的def groupAnagrams(strs): from collections import defaultdict lookup defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 lookup[tuple(count)].append(s) return list(lookup.values())这种方式在可读性上甚至更好但我面试时仍然更常听到字符串拼接的版本因为很多人的第一反应是“数组不能当 key那就转成字符串”。两种都可以关键是不要忘掉分隔符。计算一下复杂度每个字符串扫描一遍统计计数耗时 O(k)key 生成也是 O(1)因为长度固定 26n 个字符串总计 O(n × k)。空间上哈希表依然存所有字符串O(n × k)。这个解法的精髓在于它把“判断两个词是否异位词”从“排序后比较”变成了“统计后比较”时间上砍掉了 log k 因子。但你也看到了代价是代码复杂了一点需要额外设计 key。面试官真正想听的往往就是你能不能把这个 key 的设计讲明白、讲利索。4. 两种解法怎么选面试官到底想看到什么4.1 复杂度对照与适用场景整理一张表帮助你记忆解法时间复杂度空间复杂度代码复杂度最适用场景排序法O(n × k log k)O(n × k)低字符串短、数量大、第一版计数法O(n × k)O(n × k)中字符串长、追求线性、变体题注意计数法的空间复杂度仍然是 O(n × k)因为最终的答案必须返回所有原字符串。有人以为计数法节省空间其实并没有它省的是时间。如果面试里的字符串都是英文单词平均长度也就是 5 到 10 个字符排序法的 log k 几乎可以忽略两种解法跑起来几乎没有区别。但如果把输入换成 DNA 序列、长文本片段k 可能会到几千甚至上万这时候排序法每次排序都要花不少时间计数法优势就非常明显。4.2 面试时的推进策略以我自己的经验面试官面对这题通常有两条追问线。第一条顺着排序法问你能不能保证 key 不重复第二条复杂度太高了你能不能优化到线性。无论哪条落脚点都是计数法。所以我建议的回答节奏是先说暴力思路两两比较复杂度 O(n² × k)太慢再说排序法利用排序后的归一化表示O(n × k log k)最后引出计数法计数数组作为 keyO(n × k)主动分析两种方案的复杂度并指出 key 序列化的歧义问题。这套“暴力 → 优化 → 再优化 → 边界讨论”的流程比直接默写代码更能加分。面试官要的是沟通能力和思维路径不是背题。我模拟一段对话给你感觉面试官“排序法很好还能优化吗” 你“可以。既然异位词的本质是字母个数相同我可以统计每个词各字母的出现次数用计数数组作为唯一标识。因为原题限定小写字母数组长度固定 26总复杂度能降到 O(n × k)。” 面试官“数组怎么放进哈希表” 你“序列化成带分隔符的字符串或者转成不可变的元组。这里要注意分隔符不然数字会粘在一起产生歧义。”这段对话如果练熟基本上就过关了。5. 我踩过的坑边界条件与细节排查5.1 空字符串、单字符串、重复字符串先说空字符串。输入strs []时排序法得到 key计数法得到0#0#...#0都会正常分到一组输出[[]]。但有些人会在读取字符串时假设“非空”或者用if not s: continue跳过空串把结果搞丢。这个我在代码审查里见过不止一次。再说重复字符串。输入[a, a]时两个a应该放在同一个组里输出[[a, a]]而不是[[a], [a]]。很多初学者以为去重了就可以其实哈希表的 value 是列表重复元素会依次 append 进去天然保留重复项。这里完全不需要额外处理但你要能解释清楚。还有单个字符的情况[a, b]每个字符自己一组。排序法和计数法都能正常处理注意别在统计的时候越界。比如count[c - a]只有在 c 确实是小写字母时才是合法的数组下标如果混入大写字符就变负数了这是很隐蔽的运行时错误。5.2 字符范围变了怎么办原题限定小写字母但实际面试中可能问如果字符串包含大写字母、数字甚至中文解法怎么改处理方式有两种。第一种是直接扩大计数数组的规模如果字符范围是 ASCII 可打印字符可以开长度 128 的数组如果是 Unicode就开一个 65536 的数组或者干脆用Counter字典。第二种是把字符做归一化后再计数比如先统一转小写再统计或者把非字母字符单独映射到固定位置。关键原则是你定义的 key 必须对所有字符无歧义并且同一个词的不同排列得到的 key 完全一致。只要满足这两点解法数学上是正确的。前面提到的“不加分隔符会撞 key”的例子在字符范围扩大后会变得更严重。比如计数[1, 0, 11]拼成1011而[10, 1, 1]也拼成1011这在字母只有 26 个时其实很难发生因为计数数字位数有限但一旦字符串长度很长、某些字母计数能到 100 以上数字长度就不可控。所以不管范围怎么变我都建议用分隔符或固定宽度这个习惯养成后能避免很多隐藏 bug。5.3 常见问题速查表症状可能原因解决办法分组结果少了一组过滤了空字符串不要跳过空串直接参与哈希key 冲突导致错误分组计数法没加分隔符改成#拼接或使用元组超时字符串很长还用了排序法改用计数法砍掉 log k输出顺序不如预期误以为要求排序题目允许任意顺序无需排序重复字符串丢失提前做了去重value 用列表保留所有原串用了可变对象做 keyPython 里用了 list转成 tuple 或字符串这张表是我在实际刷题和帮人 review 代码时总结出来的排查问题的效率很高。6. 这道题之外相关题与学习路线6.1 从 49 题延伸出去的高频题LeetCode 里与“字母异位词计数/分组”相关的题不少我按学习顺序列一下有效的字母异位词只判断两个词是不是异位词用计数数组即可是 49 题的缩小版。找到字符串中所有字母异位词滑动窗口加计数器在长串里找短串所有异位词起始位置是计数法的典型变体。字母异位词分组就是本文这道题用哈希表聚合归一化 key。字符串的排列与 438 类似判断一个串的某个子串是不是另一个串的排列。这几道题串起来就是“计数 哈希 滑动窗口”的完整练习路线。做完这组题你会发现它们其实是同一套思路“找不变量然后用哈希表把相同的东西聚在一起”。另外最近周赛和热门 100 题里还经常出现“基本计算器”这类表达式求值题它们和本文的主题不同属于栈与缓存。“爱吃香蕉的狒狒”875这种二分答案题也是热门题里的常客但它和字符串分组完全是两套思维。刷题的时候要注意归类字符串分组题归到“哈希 归一化”表达式题归到“栈解析”每类掌握一两道代表题比盲目刷 300 题有效得多。6.2 一个刷题技巧把“分组”问题归类遇到“把具有某种相同特征的字符串分到同一组”这种要求我的第一反应永远是找一个特征提取函数。把这个函数设计好问题就解决了一大半。对字母异位词特征函数是“排序后的字符串”或“计数序列”对同字母不同大小写的词特征是“小写后的字符串”对相同频率的数字特征是“统计后的频率元组”。这种“特征 哈希表”的模式在算法题里非常通用。你可以把它理解成一个银行柜台所有特征相同的用户都走同一条通道最终站在同一队列里。设计好通道key队列自然就分好了。同样我在 LeetCode 周赛里看到不少字符串分组题本质上都可以用这套模板。你在准备面试时如果能熟练地说出“我先设计一个无歧义的 key再用哈希表聚合”面试官通常会点头表示满意。结尾一点个人体会刷了几百道题之后回头看49 题其实是一个非常典型的分水岭能 AC 的人很多但能把 key 设计讲清楚的人不多。我个人至今的习惯是遇到字符串分组题先想“特征函数”再想“哈希”最后验证边界。这一套流程帮我避免了不少隐蔽的 bug。最后再分享一个小技巧写完代码后手动跑几个极端用例再提交比如strs []、strs [a, a]、strs [, b]。这三组用例基本能覆盖 90% 的边界问题。几年前我在面试现场因为漏掉了空字符串分组结果少了一组被面试官追问后才恍然大悟从那以后再也没有犯过同样的错误。希望这篇文章能帮你把 49 题从“背答案”变成“理解答案”。刷题这件事刷的数量不重要刷出来的思考路径才是真正能带走的东西。