字母异位词分组：排序法与计数法的哈希表设计之道

做过几道 hot100 的朋友应该都有这种感觉：很多题你当时会做，过两周再看，思路全忘，只能重新翻题解。但 LeetCode 49 这道“字母异位词分组”是个例外，它属于那种一旦想通了核心思路，就再也忘不掉的题。原因倒不是它有多简单，而是它的解法背后那条“怎么为一种等价关系设计唯一标识”的思路，在真实工程里反复出现，只要你真的理解了，几乎等于顺手掌握了一类问题的通用解法。

这道题的要求用一句话说清楚：给定一个字符串数组，把字母组成相同、排列顺序不同的字符串（也就是字母异位词）分到同一个组里。示例大家都见过：输入["eat", "tea", "tan", "ate", "nat", "bat"]，输出[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]。分组内部顺序不重要，组与组之间的顺序也不重要。看起来不难，可真要动手写，很多人的第一反应是“两两比较每个字符是否相同”——这个思路一旦落到代码上，复杂度立刻失控。

这篇文章我想从题目本质、两种主流解法的设计逻辑、工程化思考、再到刷题方法，把这道题彻底讲透。不管你是刚开始刷算法题的新手，还是在准备大厂面试、华为 OD 机考，我觉得这篇都能给你一些比“背题解”更值钱的东西。

1. 这道题到底在考什么：从题目表象看本质要求

1.1 异位词分组的核心难点不是“判断”，而是“分组”

先拆一下题目。所谓字母异位词，指两个字符串包含的字母种类和每种字母的数量都相同，只是排列顺序不同。"abc"、"bca"、"cab"就是一组标准异位词。判断两个字符串是不是异位词，方案很多：排序后比较是否相等、统计每个字符频次后比较频次数组是否相等、用质数映射后比较乘积是否相等，都能做到。这步本身对大多数人不构成障碍。

真正的难点在于“分组”这两个字。分组意味着我们需要一种机制，让同一组内的字符串能快速找到彼此，而不是两两比较。这就引出了哈希表的核心用法：给每一类异位词设计一个“组标识”（key），让所有同组的字符串都映射到同一个 key 上，然后按 key 聚合。所以这道题表面考的是“如何判断异位词”，实际上考的是“如何为一个等价类设计唯一标识，并用哈希表完成聚合”。

这个认知非常关键。因为只要你想通了这一点，LeetCode 里好几个看着毫不相关的题会瞬间变得门儿清，比如“同字母异序词”变体、字符串分组类问题、甚至一些日志归类的业务题，底层全是同一套逻辑。

1.2 为什么很多人一上来就绕进“两两比较”的死胡同

我在评论区见过最多的初版解法长这样：两层循环遍历所有字符串，每两个都比较一次，看看字符组成是否相同，相同就放进一个组。思路没错，但复杂度是 O(n² * m)，其中 n 是字符串数量，m 是字符串平均长度。在 LeetCode 的测试数据规模下，如果 n 到了几千、m 到了几十，这个算法虽然“能跑”，但已经完全没有算法美感，放在面试里基本过不了。

更致命的是，哪怕只是实现这个暴力版本，也比你想象中麻烦。每两两比较一次，就要做一次频次统计或一次排序，中间还有大量重复计算。比如"eat"和"tea"比完，再拿"tea"和"ate"比，每次都在重复统计字符频次，而这些统计结果其实完全可以在最开始就只算一次。

这也解释了为什么这道题在 hot100 里的地位那么特殊。它不是一个需要什么高深算法技巧的题，而是考察你有没有“用预处理换取查询效率”的工程直觉。这种直觉在真实业务代码里，比会背十个高级算法都有用。

2. 第一版思路：排序法为什么是题解默认答案

2.1 排序法的核心原理与最小实现

排序法的思路极短：把每个字符串的字符排序后的结果作为哈希表的 key，那么互为异位词的字符串排序后一定完全相同，直接放进同一个 key 对应的列表里。代码写出来短得不像一道中等题：

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: from collections import defaultdict groups = defaultdict(list) for s in strs: key = "".join(sorted(s)) groups[key].append(s) return list(groups.values())

Java 版本也一并放出来，方便用 Java 刷题的朋友直接对照：

class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { char[] chars = s.toCharArray(); Arrays.sort(chars); String key = new String(chars); map.computeIfAbsent(key, k -> new ArrayList<>()).add(s); } return new ArrayList<>(map.values()); } }

这个解法之所以能成为题解区的默认答案，核心原因就是它用一个统一的预处理操作（排序），把所有异位词“对齐”到了同一个字符串上。"eat"排序后是"aet"，"tea"排序后也是"aet"，"ate"还是"aet"。不管原字符串长什么样子，只要字母构成相同，排序结果就必然一致。

2.2 时间复杂度的“直觉误区”与真实数据表现

很多资料会说排序法的时间复杂度是 O(n * m log m)，其中 n 是字符串个数，m 是单个字符串的最大长度。这个说法本身没错，但我见过不少读者对这个复杂度产生误解，以为 m log m 中的 log m 是很大的开销。实际上对于这道题的常规输入，字符串长度普遍不长（个位数到二三十个字符），sorted(s)的代价非常低。

我实际用 Python 跑过，这题在 LeetCode 上一万多个测试用例的情况下，排序法通常几十毫秒内完成，性能完全不是问题。所以最开始学习时，完全不用纠结“有没有更优解”，先把排序法吃透就是最快的路径。

不过排序法有一个容易被忽略的细节："".join(sorted(s))这段代码，在 Python 里sorted(s)返回的是一个个字符组成的列表，必须 join 成字符串才能当 key。漏掉这一步会直接得到TypeError: unhashable type: 'list'。这个报错我见过太多人踩了，属于典型的“思路一分钟、语法卡半天”。

2.3 为什么说排序法不是“投机取巧”

偶尔会看到有人说排序法“没技术含量”，说这题考察的是计数法，排序法只是 hack。这个观点我完全不同意。排序法抓住的是异位词的本质定义——“字母组成的多重集合相同”。一个多重集合在有序化之后，会坍缩成唯一的规范形式。这是一个数学上非常漂亮的性质，也是很多工程系统里做归一化处理时的通用手段。

举个现实案例：很多日志系统中会把不同字段顺序的 JSON 结构归一化后再做签名比对，本质就是把一个无序结构映射成一个有序字符串，用来判断两个结构是否“本质相同”。这和sorted(s)当 key 的逻辑如出一辙。所以排序法不仅不是投机取巧，反而是对“规范化处理”这个工程思想最简单、最浓缩的体现。

3. 排序之外的选择：计数法把算法复杂度压到了什么程度

3.1 计数法的设计逻辑与代码实现

排序法虽然在数据规模上够用，但它确实做了一些“额外工作”。对字符串"abcdefghijklmnopqrstuvwxyz"这种长字符串排序，需要付出 O(m log m) 的代价，可我们真正关心的只是 26 个字母分别出现几次，排序中那些字符之间的相对顺序信息对我们毫无意义。

这时候计数法就登场了。思路是：统计每个字符串中每个字母出现的次数，把 26 个计数拼成一个固定结构的 key。关键点在于，这个 key 不能是数组（数组不可哈希），也不能是直接拼接的数字（比如"1,0,2,0…"这种字符串可能产生歧义）。正确的做法是，用特殊分隔符把每个字母的计数连接成一个字符串。

class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: from collections import defaultdict groups = defaultdict(list) for s in strs: counts = [0] * 26 for ch in s: counts[ord(ch) - ord('a')] += 1 # 用 # 分隔每个计数，防止 "12,3" 与 "1,23" 这类歧义 key = "#".join(str(c) for c in counts) groups[key].append(s) return list(groups.values())

Java 版也给出：

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

这个解法的时间复杂度是 O(n * m)，去掉了排序的 log m 因子。在字符串特别长、或者这道题的变种要求极致性能时，计数法有明显优势。

3.2 计数法里的两个经典大坑

坑一：分隔符不能省。假设直接用"".join(str(c) for c in counts)拼接计数，那么一个字符串的计数序列是[12, 3, 0, ...]时，拼接结果是"1230..."；另一个字符串的计数是[1, 23, 0, ...]时，拼接结果也是"1230..."。两个不同的计数序列被映射到了同一个 key 上，异位词分组会瞬间出错。这类 bug 在真实运行中很难一眼看出来，因为不是必现，而是特定输入才会触发。

坑二：计数数组的语义要扣准。这里假设输入只包含小写字母，所以数组长度定为 26。如果题干没有明确这个约束，就不能写死 26。LeetCode 49 的题干写了“仅包含小写字母”，所以没问题；但变种题如果没有这句，你需要改成 256（ASCII 全量）或者用字典动态统计，否则等着跑出数组越界。

3.3 两种解法如何选：不是“你死我活”，而是看场景

我的建议是：面试先说排序法，把思路讲清楚，然后主动补一句“如果字符串特别长，可以用计数法把排序的 log m 因子去掉，用 26 个字母的频次拼 key”。这一句话就体现了你“知道不同方法的取舍”，在面试官那里的印象分完全不一样。至于做题阶段，两种都写一遍，你会发现计数法写完对哈希 key 设计的理解会深一大截。

4. 从哈希表设计到序列化思想：这道题真正的工程价值

4.1 为什么“找一个好 key”是这道题的核心方法论

我在刷题之外做业务开发时，经常想起这道题。因为“把一组对象按某个隐含等价关系分组”这个需求，在真实系统里太常见了。比如把一批用户按“手机号脱敏后的前三位 + 尾号四位”分组、把订单按“省 + 城市 + 商品类目”聚合、把埋点日志按“页面路径 + 来源渠道”归类。所有这些操作的底层逻辑，和 LeetCode 49 完全一致：为每个对象计算一个分组标识，标识相同就归为一组。

那什么样的标识才是一个好 key？这道题给出了两个经典的参考答案。排序法提供的思路是“规范化”——把无序的信息整理成一种不变的形式，不管输入长什么样，只要本质相同，规范化结果就相同。计数法提供的思路是“特征向量”——提取对象的核心特征，组成一个签名，签名相同即归类。这两种思路在真实系统的数据仓库建模、ETL 清洗、日志归因中频繁出现，比任何一道“为了算法而算法”的题目都更贴近工程实际。

4.2 复合 key 的序列化：从数组到字符串的转换艺术

计数法里把长度为 26 的计数数组转成带分隔符的字符串，这一操作在工程上有一个正式的名字：序列化。为什么不能直接用数组当 key？因为 Python 的 list 和 Java 的数组不是不可哈希类型，不能直接塞进 HashMap 或字典。非要塞，就得把它转成一个不可变类型。

这种“把复合结构序列化成字符串当 key”的做法在业务代码里也非常常见。比如你要缓存一个查询条件组合的查询结果，常常会把“城市 + 日期 + 渠道”拼成一个字符串作为缓存的 key；比如你在做接口幂等时，会把请求参数按字段名排序后再序列化成一个签名串，用来判断两次请求是否等价。这些基本都是 LeetCode 49 计数法思想的直接延伸。

所以我的建议是：写这道题的时候，别只满足于“AC 了”，多想想 key 的设计过程。你是在训练一种把一个业务对象抽象成一个唯一标识的能力，这种能力在你日后处理分布式任务去重、数据聚合、缓存设计时会反复用到。

5. 从 LeetCode 49 延伸到刷题方法论：hot100 到底应该怎么刷

5.1 这道题与 hot100 其他题目的隐藏关联

很多人刷 hot100 是一道一道孤立地刷，刷完就忘，原因就在这里：没有把题目和题目之间的方法论连接起来。LeetCode 49 看起来是“字符串哈希”类题目，但它的方法论和好几类题相通。

比如 LeetCode 242“有效的字母异位词”，本质上就是判断两个字符串的计数数组是否完全相等，这道题只需要一个哈希表或一个长度 26 的数组就能解。再比如 LeetCode 438“找到字符串中所有字母异位词”，考察的是滑动窗口 + 频次计数，里面的核心判断逻辑（窗口内字符频次与目标串一致）和本题的计数思想异曲同工。还有 LeetCode 347“前 K 个高频元素”，需要先统计频率再用堆排序，统计频率的部分同样依赖哈希计数。

如果你在刷 49 的时候能主动把这些题串起来看，你的学习效率会比“一天刷五道新题、每道只过一遍”高得多。这也是我刷完两轮 hot100 之后最大的体会：数量不重要，串联才重要。

5.2 华为 OD、大厂机考里这类题的实际出场方式

热词里有人问“华为 OD 算法题刷多久能过”，这个问题很难给一个绝对天数，但我可以告诉你算法题在机考中的权重结构。像 LeetCode 49 这种题，属于典型的“中等难度、高频考、代码量短”题型。它的特点是不需要太复杂的算法背景，但卡你对哈希表和字符串处理是否熟练。这类题恰恰是机考中性价比最高的一类：刷一道会的概率极高，考到就能拿分，而且不会占用太多复习时间。

具体到准备策略，我会建议把 hot100 按题型分块刷，每块挑 3 到 5 道核心题精做。字符串哈希块就选 49、242、438；滑动窗口块就选 3、76、424；二叉树块就选 102、105、124。每道题不光要会写，还要能把思路讲出来。机考和面试不一样的地方在于，机考只认最终代码的正确性和效率，但面试会问“为什么这么做”，如果你平时只背代码不思考，到了面试环节会明显露怯。

5.3 Python 和 Java 在实现上的差异细节

我在上面给了 Python 和 Java 两版代码，这里再单独说几个实际写代码时容易踩的差异点。

Python 里最顺手的数据结构是defaultdict(list)，省去了判断 key 是否存在再初始化列表的步骤。但要注意，defaultdict在力扣的类方法里没问题，可如果你在算法题之外用它处理不确定结束的循环，偶尔会因为默认值自动创建 key 而出现诡异 bug，比如遍历时字典莫名变大。所以日常用defaultdict时，最好想清楚是否有这种副作用。

Java 里的computeIfAbsent是 JDK 8 新增的，很多老项目代码里还在用“先判断 containsKey、再 get、再 put”的三板斧。刷题时用computeIfAbsent最简洁，但如果你去维护旧代码，也需要能读懂老式写法。另外 Java 的new String(chars)直接把排序后的字符数组转成字符串，这个操作是深拷贝，不会受后续数组修改影响，细节上很安全。

6. 刷题过程中的避坑记录与面试表达建议

6.1 三个最常见的真实报错与解决记录

我把这道题评论区和自己带新人时见过的报错整理了一份，按出现频率排序。

第一，TypeError: unhashable type: 'list'。原因就是用列表直接当字典 key，解决办法要么排序后转字符串，要么计数后转元组。Python 里元组可以被哈希，所以key = tuple(counts)也是可行的简化方案，不过字符串形式可读性更好。

第二，计数法拼接 key 时忘了分隔符导致不同计数序列撞 key。这个坑我在 3.2 里详细说过，最稳妥的记忆方式是：只要在把数组转字符串时把“连续数字”拼在一起，就必须加分隔符。

第三，Java 选手最容易犯的错是把Map<String, List<String>>写成了Map<String, ArrayList<String>>，编译没问题，但赋值时类型不匹配会报错。写泛型时变量类型用接口List，实例化时才用具体实现类ArrayList，这个习惯面试时也算加分项。

6.2 面试时怎么讲这道题才能拿高分

如果面试官让你做这道题，一个高分的表达结构是：先说暴力思路和它的复杂度问题，再说排序法的设计动机，最后提计数法作为优化。整个过程不要超过三分钟。

我建议你练习的时候按下面这个脚本组织语言：“异位词的特点是字母构成相同但顺序不同，所以第一反应是排序，排序后字符串相等就属于同一组，用哈希表聚合，时间复杂度 O(n·m log m)。如果字符串很长，排序的 log m 因子不划算，可以统计每个字符串的 26 字母频次，把频次序列化成一个带分隔符的字符串作为 key，时间复杂度降到 O(n·m)。”

这段话说完，面试官基本能确认两件事：你真的理解了解法，而不是背了代码；你知道有取舍，并且能讲清楚取舍依据。这两个信号在面试中比“写出了最优解”更值钱。

6.3 多语言扩展思路：Go、C++ 实现时的不同侧重点

如果你后续用 Go 或 C++ 刷题，这道题也能帮你熟悉三种语言的哈希表差异。Go 里map[string][]string的用法和 Python、Java 类似，但要注意 Go 的[]byte转string前需要先排序，排序要自己写sort.Slice或sort.Strings，没有直接对字符串内字符排序的原生函数。C++ 则可以直接对string调sort(s.begin(), s.end())，非常方便，但unordered_map的 key 用string时要注意自定义哈希的问题，默认的std::hash<string>足够好用，不用额外操心。

最后分享一个我自己刷题复盘时的小习惯：一道题 AC 之后，隔一周不看任何笔记，重新手写一遍解法；如果写不出来，就在题号旁边画个圈，一周后再来一轮。这道字母异位词分组，我前前后后手写了四遍，每一遍都比上一次更接近“不用思考直接写出来”的状态。到后来面试时被问到变种题，我几乎不用过脑子就能想到“这不就是序列化数组当 key 吗”的思路上来。刷题说到底拼的不是谁的智商高，而是谁在正确的方向上多重复了几次。