LeetCode LCR 033. 字母异位词分组
目录
题目描述
题意分析
给一组字符串，把互为变位词（字符组成完全相同、仅顺序不同）的放进同一组，返回所有分组。组与组之间、组内元素之间的顺序都不作要求，这条「顺序任意」大幅降低了实现负担——不需要维护出现次序。
「互为变位词」是一种等价关系：自反、对称、传递都成立。等价关系的分组问题有一个标准形态——为每个元素计算一个规范形式（签名），签名相同的自动落进同一组。于是问题从「两两比较」转成「如何为一个字符串定义签名」。
两两比较的代价是平方级：
n个字符串要比 $O(n^2)$ 对，每对还要 $O(k)$ 的判定。而签名方案只需要对每个字符串算一次签名，然后按签名归拢，是线性次的操作。签名必须满足两个性质：互为变位词的字符串签名相同（完备），不互为变位词的签名不同（无冲突）。字符组成完全刻画了变位词关系，所以任何能唯一表示「字符多重集合」的东西都可以当签名。
约束里字符串仅含小写字母，这个信息决定了签名可以做得很廉价：字符集只有 26 种。边界要覆盖：空字符串（它自成一类）、只有一个字符串的输入、以及完全相同的两个字符串（它们当然互为一组）。
解法：哈希表统计状态
核心思路
暴力做法是两两判断是否互为变位词再并查集式地合并，$O(n^2 k)$ 时间，
n大时不可接受。瓶颈在于「两两比较」这个组织方式本身——等价关系不需要逐对验证，只要能给每个元素算出规范形式，归组是自动完成的。于是核心问题变成：给一个字符串设计一个只依赖字符组成、与顺序无关的签名。把字符串的字符排序后拼回字符串，就是最直接的规范形式：
"eat"、"tea"、"ate"排序后都是"aet"，而"tan"、"nat"都是"ant"。排序抹掉了顺序信息，恰好只保留了我们关心的多重集合。这个签名同时满足完备与无冲突：互为变位词意味着字符多重集合相同，排序结果必然一致；反之排序结果一致意味着逐位字符相同，多重集合自然相同。两个方向都成立，所以它是一个合格的规范形式。
有了签名，剩下的就是分组。用一个映射
d，键是签名、值是该签名对应的原字符串列表。遍历输入，算出签名后把原串追加到对应的列表里。这里的不变量是：任意时刻d中每个键值对，都表示「签名为该键的、已被处理过的全部原字符串」。注意存进列表的必须是原字符串而不是排序后的签名——题目要返回的是原始输入，签名只是分组的中间产物。
遍历结束后把
d的所有值收集成结果即可。因为题目不要求任何顺序，直接取映射的值集合，不需要额外排序。值得一提的另一种签名：既然字符集只有 26 个，也可以用长度 26 的计数数组拼成形如
"a2b1..."的字符串作签名，这样算签名是 $O(k)$ 而非 $O(k \log k)$。它更快，但拼装逻辑更长；本题字符串通常很短，排序签名在面试里写起来更快也更不易错，两者都是标准答案。
解题步骤
- 准备映射：
Map<String, List<String>> d，键是签名、值是原串列表。选哈希映射而不是有序映射，是因为结果不要求顺序，哈希的平均 $O(1)$ 查找更划算。- 逐串计算签名：
char[] t = s.toCharArray(); Arrays.sort(t); String k = String.valueOf(t);。必须先转成字符数组再排序，因为字符串本身不可变；排序抹掉顺序、保留组成，这正是签名的定义。- 按签名归组：
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s)。这一句同时完成「键不存在则建空列表」和「追加元素」，比先containsKey再get少一次哈希查找，也避免了漏建空列表导致的空指针。- 追加的是
s而不是k：签名只用于分组，返回值必须是原始字符串，写错会让输出全变成排序后的乱码。- 收集结果：
new ArrayList<>(d.values())。题目不限定组间与组内顺序，直接取值集合即可，无需再排序。Go 版同理，遍历map把每个值切片追加进结果。以
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]走一遍。处理
"eat"：排序得签名"aet"，映射中无此键，新建列表并追加，d = {"aet": ["eat"]}。处理"tea"：排序同样得"aet"，命中已有键，追加得d = {"aet": ["eat", "tea"]}。处理"tan"：排序得"ant"，新建，d = {"aet": ["eat","tea"], "ant": ["tan"]}。处理"ate"：签名"aet"，追加，第一组变成["eat","tea","ate"]。处理"nat"：签名"ant"，追加，第二组变成["tan","nat"]。处理"bat"：排序得"abt"，与前两个签名都不同，新建第三组["bat"]。遍历结束，
d有三个键，取出所有值得到[["eat","tea","ate"], ["tan","nat"], ["bat"]]。组的先后顺序取决于哈希遍历顺序，题目允许任意排列，所以都算正确。再看两个边界：输入含空字符串
[""]时，签名也是空串，自成一组返回[[""]]；输入含两个完全相同的串["ab","ab"]时，两者签名都是"ab"，落进同一组返回[["ab","ab"]]——相同字符串当然互为变位词，不应该去重。
代码实现
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 键是排序后的签名，值是该签名对应的全部原字符串。
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
char[] t = s.toCharArray();
// 排序抹掉顺序、保留字符组成，正是变位词的规范形式。
Arrays.sort(t);
String k = String.valueOf(t);
// 存进去的必须是原串 s，签名只用于分组。
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}
func groupAnagrams(strs []string) (answer [][]string) {
// 键是排序后的签名，值是该签名对应的全部原字符串。
d := map[string][]string{}
for _, s := range strs {
t := []byte(s)
// 排序抹掉顺序、保留字符组成，正是变位词的规范形式。
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
k := string(t)
// 存进去的必须是原串 s，签名只用于分组。
d[k] = append(d[k], s)
}
for _, v := range d {
answer = append(answer, v)
}
return
}
复杂度分析
- 时间复杂度：$O(nk \log k)$，
n是字符串个数、k是字符串的最大长度。每个字符串排序一次是 $O(k \log k)$，建签名与哈希写入是 $O(k)$，共n次；最后收集结果是 $O(n)$。若改用 26 位计数数组作签名，可降到 $O(nk)$。- 空间复杂度：$O(nk)$。映射的键存了
n个长度不超过k的签名，值里存的是原字符串的引用总量也是 $O(nk)$ 级；除此之外每次排序的临时字符数组是 $O(k)$，可复用。
关键点总结
- 分组问题先判断分组依据是不是等价关系，是的话就去找「规范形式」，把 $O(n^2)$ 的两两比较降到 $O(n)$ 次签名计算，这是分组类题目的通用降维手段。
- 签名必须双向成立——同组必同签名、同签名必同组，设计完要在心里各验一个方向，只验一边容易造出有冲突的签名。
- 排序字符串是最省事的规范形式；字符集有限时用定长计数拼装的签名更快，两者的取舍点在于
k的大小与代码复杂度，面试时值得主动提一句。computeIfAbsent这类「不存在则创建再操作」的写法能同时消灭空指针和重复查找，处理「映射到集合」的结构时应当形成肌肉记忆。- 存进结果的是原串而不是签名，中间产物与返回值不要混用——这是所有「先变换再归组」类题目的共同陷阱。
- 面试视角：写完排序签名版本后主动说明「字符集只有 26，可以换成计数签名把复杂度降到 $O(nk)$」，并指出计数签名要用分隔符（如
a2b1而非21）避免a11b1与a1b11之类的歧义。能讲出这个歧义点比单纯报复杂度更有说服力。
易错点总结
- 把签名而不是原串存进结果：
["eat","tea"]会输出[["aet","aet"]]，返回的不再是输入中的字符串。- 计数签名不加分隔符：
"aaab"与"aabbb"之类的组合在拼接数字时可能撞成同一个键，把本不同组的字符串错误合并。- 直接对
String调排序而不转字符数组：Java 的String不可变，没有原地排序方法，误用会编译失败或写出低效的逐字符插入。- 用
containsKey后忘了在缺失时新建列表：直接d.get(k).add(s)会在首次遇到某签名时对空引用调用方法，抛空指针异常。- 对相同字符串做去重：
["ab","ab"]应返回[["ab","ab"]]，去重会丢掉一个元素，题目要的是分组不是集合。- 用字符相加或异或作签名：
"abc"与"aad"（若存在这样的组合）字符和相同却不是变位词，和/异或都不能唯一表示多重集合，会把不同组合并。- 忽略空字符串：
[""]的签名是空串，若代码里对空串提前跳过，结果会少一组。- Go 里对
string直接排序：string是不可变的字节序列，必须先转[]byte或[]rune；若字符集扩到多字节字符还要用[]rune，按[]byte排序会把一个字符拆散。- 为了让输出顺序稳定而对组内排序：题目不要求顺序，额外排序只增加 $O(nk \log n)$ 的开销，属于多余动作。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 49. 字母异位词分组 | 中等 | 与本题同题，可直接套用签名分组 |
| 面试题 10.02. 变位词组 | 中等 | 与本题同题，可直接套用 |
| 242. 有效的字母异位词 | 简单 | 只做两串之间的判定，不需要签名与映射，直接比对频次数组即可 |
| LCR 032. 有效的字母异位词 | 简单 | 两串判定的变体，额外要求两串顺序不完全相同才算变位词 |
| 383. 赎金信 | 简单 | 判的是单向包含而非相等，计数只要不小于零即可，长度可以不同 |
| 451. 根据字符出现频率排序 | 中等 | 同样先统计频次，但接下来要按频次降序重建字符串而非归组 |
| 1002. 查找共用字符 | 简单 | 对多个字符串的计数逐位取最小值，考察的是计数向量的交集运算 |
| 791. 自定义字符串排序 | 中等 | 同样要按规则重排字符，但排序依据来自外部给定的字符优先级 |