字母异位词分组：分拣工厂如何设计 key？

Anagram Sorting Factory · 字母分拣工厂

每个单词是传送带上的发光货物。中间的标准化机器生成顺序无关的 key，右侧 HashMap 仓库按 key 分桶——桶里存的是原词，不是排序后的字符串。

经典输入

["eat", "tea", "tan", "ate", "nat", "bat"]

传送带 → 标准化机器 → 仓库桶

异位词的问题，本质不是比较两个字符串长得像不像，而是设计一个身份证。只要两个单词的身份证一样，它们就应该进同一个组。排序 key 的作用，就是把 eat、tea、ate 都变成 aet。

Step 1/11 · 工厂开工

输入传送带6 件货物

eat

tea

tan

ate

nat

bat

字母标准化机器排序 key

货物即将进入标准化流水线…

HashMap 仓库0 个桶

等待第一个 key…

这一步在讲什么

欢迎来到字母分拣工厂。每个单词是传送带上的货物；中间机器负责生成「顺序无关的 key」；右侧 HashMap 仓库按 key 分桶存放原词。

异位词的问题，本质不是比较两个字符串长得像不像，而是设计一个身份证。只要两个单词的身份证一样，它们就应该进同一个组。

计数 key 优化

两种 key 设计思想等价（小写字母集），切换看中间机器如何变化。

方案 A：排序 key

word = "eat" → sorted(word) = "aet"

复杂度: O(n · k log k)
优点: 简单、面试最容易写
缺点: 每个单词都要排序

方案 B：26 位计数 key

eat → [a:1, e:1, t:1] · tea → [a:1, e:1, t:1]

复杂度: O(n · k)
优点: 更快
缺点: 字符集需固定（如仅小写字母）

Go 代码 · 逐行高亮

key 策略：sortedKey

1func groupAnagrams(strs []string) [][]string {
2    groups := make(map[string][]string)
3 
4    for _, word := range strs {
5        key := sortedKey(word)
6        groups[key] = append(groups[key], word)
7    }
8 
9    result := make([][]string, 0, len(groups))
10    for _, bucket := range groups {
11        result = append(result, bucket)
12    }
13    return result
14}

不变量

两个单词同组 ⇔ 它们生成的 key 相同。

常见误区

直接用原字符串当 key：会把 eat 和 tea 拆开。
只看出现过哪些字母：会把 ab 和 abb 混淆。
两两比较所有字符串：能做但低效，不如一次扫描进 map。

执行轨迹表

点击行跳转

Step	当前单词	生成 key	map 操作	当前分组结果	阶段
0	—	—	—	—	工厂开工
1	eat	eat	map["eat"] = ["eat"]	[eat]	错误 key · eat
2	tea	tea	map["tea"] = ["tea"]	[eat] · [tea]	错误 key · tea
3	—	—	❌ 分组失败	[eat] · [tea]	错误 key 警告
4	eat	aet	map["aet"] = ["eat"]	[eat]	分拣流水线
5	tea	aet	append → map["aet"]	[eat, tea]	分拣流水线
6	tan	ant	map["ant"] = ["tan"]	[eat, tea] · [tan]	分拣流水线
7	ate	aet	append → map["aet"]	[eat, tea, ate] · [tan]	分拣流水线
8	nat	ant	append → map["ant"]	[eat, tea, ate] · [tan, nat]	分拣流水线
9	bat	abt	map["abt"] = ["bat"]	[eat, tea, ate] · [tan, nat] · [bat]	分拣流水线
10	—	—	return values(map)	[eat, tea, ate] · [tan, nat] · [bat]	完成汇总

面试回答

我会用 HashMap 分组。关键是给每个字符串生成一个规范化 key。最直接的方法是把字符串排序，例如 eat、tea、ate 排序后都是 aet，所以它们会落到同一个桶里。遍历所有字符串，把原字符串追加到 map[key]，最后返回 map 的所有 value。排序版复杂度是 O(n·k log k)。如果字符集固定为小写字母，也可以用 26 位计数数组作为 key，把复杂度优化到 O(n·k)。