LeetCode 49. 字母异位词分组
目录
题目描述
题意分析
输入一个字符串数组，要求把互为字母异位词的字符串归到同一组，返回所有组；组与组之间、组内元素之间的顺序都不作要求。字母异位词的定义是：两个串用到的字母完全相同、每个字母出现的次数也完全相同，只是排列顺序不同。
判断两个串是否互为异位词很容易，难的是「分组」。如果两两比较，$n$ 个串就要比 $O(n^2)$ 次，数组长度上限是 $10^4$，这个量级已经接近超时，更别说每次比较本身还要 $O(k)$。所以真正要找的不是「比较方法」，而是一个能代表整组的签名：让同组的串算出同一个签名、不同组的串算出不同签名，然后按签名一次归拢。
题面同时点明了两种签名的取法。约束里写明字符串只含小写英文字母，于是签名可以是「把字符排序后的字符串」——异位词排序后必然完全一致；也可以是「$26$ 位的字符计数签名」——统计每个字母出现次数，再把这 $26$ 个数字拼成一个串，同样能唯一刻画一组异位词。前者好写，后者更快。
边界要注意：数组里可能出现空字符串，它的签名就是空串，会自成一组（若有多个空串则归在一起）；也可能有完全相同的两个串，它们当然是异位词，必须留在同一组里而不能去重。
解法：排序字符串作为哈希 key
核心思路
分组的关键不是两两比较，而是为每个字符串构造一个能唯一表示其字符组成的签名。将字符串排序后，字符种类和出现次数相同的异位词会得到同一个结果，例如
eat、tea、ate的签名都是aet；字符组成不同，排序结果也一定不同。因此用哈希表维护
签名 -> 原字符串列表。循环不变量是：处理完前 $i$ 个字符串后，哈希表已经正确保存这 $i$ 个字符串的全部分组。处理下一个字符串时只需计算签名并追加到对应列表，不会影响已有分组。正确性来自排序签名的充要性：两个字符串互为异位词，当且仅当它们排序后的字符串相同。所以同组元素不会被拆开，不同组元素也不会被合并。这里保留排序法作为面试主解法；若面试官要求去掉排序，可改用 $26$ 位字母计数作为签名。
解题步骤
- 创建哈希表，键是排序签名，值是属于该签名的原字符串列表。
- 遍历每个字符串，将其转成字符数组并排序，得到签名
key。- 若
key第一次出现就创建列表，然后把原字符串追加进去；重复字符串也要保留，因此不能用集合。- 遍历结束后收集哈希表的所有值。题目不要求组间和组内顺序，无需额外排序。
例如
eat和tea都进入键aet对应的列表，tan和nat都进入键ant对应的列表，bat则进入键abt对应的列表，最终自然形成三组。
代码实现
import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
// 排序后的 key 相同，说明字符组成完全一致。
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
}
import "sort"
func groupAnagrams(strs []string) [][]string {
groups := make(map[string][]string)
for _, str := range strs {
chars := []byte(str)
sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
key := string(chars)
groups[key] = append(groups[key], str)
}
res := make([][]string, 0, len(groups))
for _, group := range groups {
res = append(res, group)
}
return res
}
复杂度分析
- 时间复杂度：$O(n \cdot k \log k)$，其中 $n$ 是字符串数量，$k$ 是字符串的最大长度；主要开销是逐个排序。使用定长计数签名可降为 $O(n \cdot k)$。
- 空间复杂度：$O(n \cdot k)$，用于排序副本、签名和分组结果；若不计返回结果，哈希表中的签名仍可能占用同量级空间。
关键点总结
- 先找能唯一表示一个等价类的签名，再用哈希表分组，避免 $O(n^2)$ 的两两比较。
- 排序签名简单通用；仅含小写字母时，计数签名能省去排序。
- 签名只用于查表，答案列表中保存的必须是原字符串。
- 计数签名要带分隔符或固定宽度，否则不同计数组合可能拼成同一个字符串。
易错点总结
- 把排序后的
key加入列表，会丢失原字符串；签名只当键使用。- Java 的
char[]按引用比较，不能直接作为内容签名，必须转成String。- 用
Set保存分组会错误地去掉重复字符串，例如["ab", "ab"]必须保留两个元素。- 只用长度或字符码之和作为签名会碰撞，例如
abc与aad的长度和字符码之和都相同，但它们不是异位词。- 空串的排序签名仍是空串，是合法的哈希键，不能跳过。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 242. 有效的字母异位词 | 简单 | 单对异位词判定 |
| 383. 赎金信 | 简单 | 计数覆盖关系 |
| 387. 字符串中的第一个唯一字符 | 简单 | 计数后二次扫描 |
| 438. 找到字符串中所有字母异位词 | 中等 | 定长滑窗匹配计数 |
| 451. 根据字符出现频率排序 | 中等 | 按频次重排输出 |
| LCR 032. 有效的字母异位词 | 简单 | 变形、需排除相同串 |
| LCR 033. 字母异位词分组 | 中等 | 同型题、分组签名 |
| 剑指 Offer 50. 第一个只出现一次的字符 | 简单 | 有序哈希取首个 |
| 面试题 01.01. 判定字符是否唯一 | 简单 | 位图去重 |
| 面试题 01.02. 判定是否互为字符重排 | 简单 | 计数相等判定 |
| 面试题 01.04. 回文排列 | 简单 | 奇数计数至多一个 |
| 面试题 10.02. 变位词组 | 中等 | 同型题、变位词分组 |