LeetCode 49 字母异位词分组：哈希key设计是通关关键

如果你刷过LeetCode，尤其是按着“热门100题”列表一路练过去，那第49题《字母异位词分组》大概率是你很早就碰到的又高频又亲民的一道。我第一次刷它的时候，觉得这题不过如此，无非是排序一下、用哈希表存一存。可后来在一次模拟面试里，被面试官顺着这道题追问了几轮，才发现自己之前的理解只停留在“背解法”的层面，离“讲清楚为什么”还有很大距离。今天不打算只贴一遍题解，而是把这道题从题意、思路、代码到坑位完整拆开，聊聊为什么它会被反复选中，以及下次遇到它的变体时，你可以怎么快速应对。

先看它到底解决了什么问题：给定一个字符串数组，需要把“字母组成完全相同、只是顺序不同”的单词分到同一组。比如["eat", "tea", "tan", "ate", "nat", "bat"]，eat、tea、ate就是一组，tan和nat是一组，bat单独一组。这题适合谁来刷？准备技术面试的、刚开始刷LeetCode想建立哈希表感觉的、或者面试前想快速过一遍高频题的，都能从里面拿走不少东西。它表面考的是“字符串处理”，实际上核心考的是：你怎么给一堆元素设计一个合理的哈希key。这个能力，比这道题本身值钱得多。

1. 题目拆解：为什么它是一道“哈希表入门课”

1.1 题目到底在问什么

题目信息量不大，但有一个前提条件很容易被忽略：字符串只包含小写字母。这意味着整套解题方案都建立在“26个字母”这个有限集合上。你要是忽略这个前提，用了一个非常通用的方案也能跑过，但面试官问“如果字符集变成整个Unicode，你的方案还能用吗”的时候，你就会开始冒汗。

异位词的定义是：两个字符串中每个字符出现的次数完全相同。什么叫“次数完全相同”？anagram和nagaram就是一对异位词，a出现3次、n出现1次、g出现1次、r出现1次、m出现1次，两边完全对得上。判断异位词的本质，是判断两个字符串的“字符频率分布”是否一致，而不是看它们是否“长得像”。

有了这个视角，题目就从“怎么找一堆词的共同点”变成了“怎么把相同频率分布的词映射到同一个标记上”。一旦你想通了这一点，后面所有解法都只是“选什么标记”的问题。

1.2 核心考点：哈希key的设计

这道题能被选进热门100题，不是因为算法多复杂，而是因为它完美地集中考察了三个基本功：

• 哈希表的灵活运用：你要知道用什么作为key，什么作为value。
• 字符串的高效处理：排序、遍历、拼接，哪个场景用哪种方式。
• 时间复杂度的直觉：同一个思路，不同实现能差出好几倍性能。

这三点组合起来，正好是面试官喜欢的“30分钟手写题”形态。它不像动态规划那样需要灵光一现，也不像系统设计那样需要广博知识，它就是实打实地考察你会不会“把一个直观想法落地成高效代码”。

1.3 一句话理解“分组”的数学本质

把异位词分组，其实是在做“等价类划分”。数学里的等价关系要求自反、对称、传递，“字母组成相同”恰好满足这三个条件。所以整个数组可以划分成若干个不相交的集合，每个集合内部任意两个元素互为异位词。

这个数学背景不是废话，它帮你建立了一个正确的心理模型：你需要找到一个函数 f，把每个字符串映射到一个“规范化表示”上，使得两个字符串互为异位词，当且仅当 f(s1) == f(s2)。找到这个f，题目就做完了。常见的f有两种：一种是“排序后的字符串”，另一种是“字符计数数组的某种编码”。接下来的思路部分，就是围绕这两个f展开的。

2. 两种核心解题思路：排序分组与计数哈希

2.1 思路一：排序后作为key

这应该是绝大多数人想到的第一个方案。原理特别朴素：既然异位词的字母组成相同，那把每个字符串内部的字母按字典序排一遍，所有异位词都会变成同一个字符串。

举个例子就非常清楚了：

• eat排序后变成aet
• tea排序后变成aet
• ate排序后变成aet
• tan排序后变成ant
• nat排序后变成ant

于是你用aet做key，就能把三个词串到一起；用ant做key，就能把另外两个词串到一起。这个方案的优美之处在于，你不需要手动比较任何两个字符串，所有工作都交给排序和哈希表完成。

实现上有一个细节值得注意：Java里对字符串排序不是直接操作String，而是先转成char[]，然后调用Arrays.sort，再把排好序的字符数组new回String。这个“转来转去”看起来很绕，但其实是Java字符串不可变这个特性决定的。Python就舒服一点，sorted(s)直接返回字符列表，''.join(sorted(s))拼回字符串就行。

2.2 思路二：计数数组作为key

第二种思路更贴合“频率分布”这个本质。既然只有26个小写字母，那我干脆用一个长度为26的整型数组，记录每个字母出现的次数。两个字符串互为异位词，当且仅当它们的计数数组完全相同。

比如eat的计数数组是[1, 0, 0, 0, 1, ..., 0, 1, ...]（a、e、t各出现一次），tea的计数数组和它完全一样。理论上这个数组就能当key。但它有个绕不开的问题：Java和Python里，数组默认不是哈希表能直接用的key类型。Python的list不可哈希，Java的int[]没有合适的equals和hashCode。所以你还需要把计数数组“编码”成一个可哈希的字符串或者元组。

Python里最简单的做法是转成tuple(cnt)，因为tuple是不可变的、可哈希的，直接塞进字典完全没问题。Java里一般做法是把非零的字母和它的计数拼成字符串，比如a1e1t1。这里我提醒一下：如果你想把计数直接按顺序拼起来，比如“111000...”这样，一定要小心歧义问题。当一个字母出现超过9次时，直接拼接的数字串会变得难以解析，所以官方题解里才会用#作为分隔符，比如1#0#0#1#...#1，每个计数之间用分隔符隔开，这样不管出现多少次都不会歧义。这是我建议你在面试时主动提一嘴的细节，非常加分。

2.3 两种思路的对比：什么时候用哪个

这里我列一个表格，把两种思路放在一起对比，你就能更直观地看到它们的取舍：

从纯理论上说，计数法的时间复杂度更优，因为排序有k log k的代价。但在实际刷题和面试里，排序法反而是我更推荐优先讲的那个方案。原因很简单：它的思路一句话就能说清楚，代码几乎不会写错，就算面试官追问，你再补计数法也会显得逻辑递进很自然。真到了每行代码都要抠性能的工程场景，那又是另一套考虑了。

3. 实操演示：代码实现与逐步讲解

3.1 Python实现：排序法

先上最经典的Python排序解法，这也是LeetCode社区里最常见的版本：

import collections def groupAnagrams(strs): mp = collections.defaultdict(list) for s in strs: key = ''.join(sorted(s)) mp[key].append(s) return list(mp.values())

核心逻辑就五行，但有几个值得展开说说的点。

第一，collections.defaultdict(list)比普通的dict方便很多。如果你用普通字典，每次添加前都要判断key存不存在：

if key not in mp: mp[key] = [] mp[key].append(s)

用defaultdict(list)之后，访问不存在的key会自动创建一个空列表，代码直接从三行变一行。

第二，''.join(sorted(s))这里sorted(s)返回的是字符组成的列表，比如sorted("eat")是['a', 'e', 't']，join把它拼回普通字符串。有的人会问，为什么不用s.sort()？因为字符串是不可变的，Python里字符串根本没有sort()方法，必须借助sorted()返回新列表。

第三，最后返回list(mp.values())，直接把字典中所有分组列表收集起来，正好是题目要求的List[List[str]]结构。这里需要注意的是，每组内部的顺序和组的排列顺序都是不确定的，但题目不要求顺序，面试时也一般不要求，所以直接返回即可。

3.2 Java实现：排序法

Java版本比Python多几行，因为字符串处理绕一些：

import java.util.*; public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> 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()); }

toCharArray()把字符串拆成字符数组，Arrays.sort原地排序，然后new String(arr)把排好序的字符数组拼回字符串。这一套组合拳是Java面试中极其高频的写法，建议直接刻进肌肉记忆。

computeIfAbsent是Java 8引入的方法，意思是“如果key不存在，就用后面的lambda表达式创建一个新列表”，存在就直接返回已有列表。这样一行就把“查key、建列表、取列表”三个动作合并了。如果你在用老的JDK，或者面试官让你写更通用的版本，可以用：

if (!map.containsKey(key)) { map.put(key, new ArrayList<>()); } map.get(key).add(s);

两种写法都要会，因为有些面试官会对Java 8语法不太熟悉，你用一段更朴素的代码反而更稳。

3.3 Java实现：计数哈希法

接着是计数法。我在面试中更看好这个实现，因为它能体现你对“频率分布”的理解：

import java.util.*; public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { cnt[c - 'a']++; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < 26; i++) { if (cnt[i] > 0) { sb.append((char) ('a' + i)).append(cnt[i]); } } String key = sb.toString(); map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); }

这段代码的核心是构造key的方式。我用的是“字母+出现次数”的非零拼接，比如eat会生成a1e1t1，tea也会生成a1e1t1。这种方法不需要固定长度，也不需要用#分隔，因为格式是“字母+数字”交替出现，解析时不会有歧义，a1永远不会被理解成别的含义。

不过我得坦白说一个实际观察：LeetCode官方题解里更常用的是固定26长度的带#分隔版本，比如"1#0#0#1#0#...#1"。它更稳，但key会很长。我用“字母+次数”非零拼接，在字符串都比较短的时候key更紧凑，内存表现更好。两种都可以，面试时选一种你最有把握的讲就行。

3.4 复杂度分析：别只记结论，要知道怎么算

复杂度是面试必问的，这里我带你手算一遍。

记n为字符串数量，k为字符串平均长度。排序法对每个字符串做一次排序，排序本身是O(k log k)，所以总复杂度是O(n * k log k)。空间上，哈希表需要存储所有字符串的引用，同时每个key需要占用排序后字符串的空间，整体是O(n * k)。

计数法省去了排序，对每个字符串只做一次长度为k的遍历来统计，然后做一遍长度为26的遍历来生成key，所以总复杂度是O(n * k + n * 26)，写成O(n * k)就行。空间同样是O(n * k)，但key的存储开销一般会比排序法更小一点。

有个有意思的工程细节：理论排序法更慢，但在LeetCode实测中，当k非常小（大部分单词就三五个字符）时，排序法的实际耗时和计数法几乎一样，因为Arrays.sort对小型数组有极高的优化，常数特别小。这就是为什么两种解法都在社区里大量存在，没有一个能以绝对优势碾压另一个。面试时你优先讲排序法完全没问题，等被追问“能不能再快一点”时，再自然引出计数法。

4. 常见问题与排查技巧实录

4.1 踩坑点一：空字符串和单字符字符串

空字符串排序之后还是空字符串，计数数组全为0，所以所有空字符串都会归到同一组，这是符合预期的。单字符字符串也很好处理，排序后还是它自己，计数数组只有一个位置为1。这两个边界情况看起来简单，但很多人会忘记在代码里显式验证，尤其是用手写测试用例时容易漏掉。建议写完解法后，先用这几个输入自测：

["", "a", "b", "ab", "ba", "abc", "cba"]

确保空字符串组、单字符组都正常划分。

4.2 踩坑点二：大小写问题

题目明确说只有小写字母，这给了我们很大的简化空间。但面试官很喜欢在这个前提上做文章，比如问“如果字符串里混合了大写字母怎么办”。这时候计数数组就不能只开26了，至少要开到52，或者统一转成小写再处理。排序法的好处在这里体现出来了，排序本身跟大小写无关，但要注意Arrays.sort排序时大写字母在小写字母前面，这会影响key的生成。如果想把"Eat"和"eat"视为同一组，需要先转成同一种case。

4.3 踩坑点三：用可变对象当key

Python里一个很隐蔽的坑是，有人会试图直接用list当key：

cnt = [0] * 26 # ...统计... mp[cnt].append(s) # 报错：unhashable type: 'list'

list是可变的，不能作为字典的key。你必须先转成tuple。Java里也同样，如果你想用数组直接当HashMap的key，会得到错误的比较结果，因为数组继承的是Object的equals和hashCode，比较的是引用地址，两个内容完全相同的数组也会被当成不同key。这个问题我见不少人踩过，尤其是在IDE里调试半天才发现。

4.4 踩坑点四：分组内部的顺序被额外排序

题目只要求分组，不要求组内单词有序。但有些同学会下意识地对每组里的单词再做一次排序，觉得这样输出更好看。这在功能上没有错，但白白增加了一部分时间复杂度，而且面试官会觉得你对复杂度不够敏感。除非面试官明确要求“输出有序”，否则不要做多余的操作。LeetCode的判题器只检查分组内容是否匹配，不关心顺序。

4.5 排查技巧：如何快速定位错误

如果你写完代码提交发现样例过不了，我建议你按这个顺序排查：

1. 先打印中间key：把每个字符串计算出的key打印出来，看是不是符合预期。排序法的key对不对一目了然；计数法的key如果出现难懂的格式，先检查计数统计是否正确。
2. 再检查字母偏移：Java里cnt[c - 'a']++，Python里ord(ch) - ord('a')，差一个ord或char转换就会导致key错乱。
3. 最后检查边界输入：看看空字符串、重复字符串、极长字符串是否都能正常运行。

有一次我帮人排查，他的计数法输出全乱了，最后发现是拼接key时忘记把字符转回来，直接把数字和字符ASCII码拼到一起，整个key变成了天书。这类问题，其实只要你打印一次中间结果，立刻就能发现。

5. 面试追问与刷题延伸

5.1 面试官会怎么追问

这道题在面试中的出场方式通常是：你写完排序法，面试官点点头，然后开始一连串追问。我整理了几个高频追问，你可以提前准备：

• 追问一：如果单词很长怎么办？这时排序法O(k log k)的代价会变得明显，计数法O(k)的优势就体现出来了。你可以顺势补充“当字符串长度很大时，计数法明显更有优势”。
• 追问二：如果字符集不只是小写字母呢？对排序法影响不大，对计数法影响很大，因为数组要扩大到对应字符集的大小。如果字符集不确定，排序法的通用性更强。
• 追问三：能不能用位运算加速？这个属于进阶方案，比如用long型变量的每一位表示字母是否出现。但要注意，位运算只能表示“出现与否”，无法表示“出现次数”，所以严格来说它不能完整解决此题，但对于某些变体（比如只需要判断是否存在异位词）是有用的。这个可以当作谈资，不建议放在最初的解法里。
• 追问四：有没有可能设计出一种完美的哈希函数，让key的长度和字符串长度无关？理论上计数法已经接近这个目标，但key的编码长度还是和字母种类有关。如果进一步压缩，可以用质数乘积的思路，把每个字母映射为一个质数，然后把字符串所有字母对应质数相乘，异位词的乘积一定相等。但这个方案在实际中不常用，因为乘积会非常大，容易溢出。不过作为面试的拓展思路，时不时能收到奇效。

5.2 和这道题同源的LeetCode题目

这里有一组和49题关系很紧密的题，建议放到一起刷：

你按“242 → 49 → 438”这个顺序刷下来，对“计数数组+哈希”这套组合拳会非常熟。这个套路在很多字符串题目里都能复用。

5.3 和近期热门题的横向对比

最近热词里出现了“基本计算器leetcode”和“leetcode 073 爱吃香蕉的狒狒”，这其实是另外两个高频考点的代表。49题属于“哈希表+字符串处理”的经典组合，基本计算器属于“栈+表达式解析”的经典组合，爱吃香蕉的狒狒属于“二分答案”的经典组合。它们彼此独立，但都是面试高频。我见过很多人在哈希类题目上花了不少时间，却忽略了二分查找类题目的训练，结果面试碰到爱吃香蕉的狒狒就卡住了。建议你在刷题的时候，按“哈希、双指针、二分、动态规划、图论、栈”几个大模块均匀分配时间，不要只盯着某一类题刷。

5.4 一个字节的思考：从这道题到系统设计

说实话，49题本身很简单，但如果你愿意多想一步，它其实藏着一点系统设计的影子。“如何把大量文本按相似度分组”在搜索引擎、日志聚类、推荐系统里都是真实问题。虽然实际系统不会用“排序后当key”这种粗暴方式，但“把复杂对象映射到规范化表示，再按规范化表示聚合”这个思路，在很多分布式框架里都能看到影子。比如MapReduce的shuffle阶段，本质上就是“按key聚合”。这么一想，一道LeetCode题和工程实践的距离其实没有想象中那么远。

写在最后：我的一点实际体会

我从49题里得到最深的一个体会是：哈希表的难点从来不是哈希表本身，而是key的设计。你设计出来的key能不能做到“同组必同key、不同组必不同key”，直接决定了答案正确与否。面试时哪怕coding能力弱一点，只要你能把这个思路清晰地讲出来，面试官一般都会给你不错的评价，因为这道题考的就是你有没有建立这种“先设计key，再想实现”的思维习惯。

最后分享一个小技巧：刷这类分组题的时候，先别急着写代码，拿出一张纸，随便列几个输入，手动算出它们的key。等你能徒手把key算明白了，代码只是顺理成章的事。这题我刷了三遍，每遍都有新收获——第一遍学解法，第二遍学复杂度，第三遍才发现它在考察等价类划分的思想。希望你不用像我一样刷三遍才意识到这些。