LeetCode 49. 字母异位词分组
题目描述
题意分析
将互为字母异位词的字符串放到同一组。异位词可以改变字母顺序，但每种字母出现的次数必须完全相同；仅仅字母种类相同或字符串长度相同都不够。
输入只包含小写英文字母，可以包含空字符串和重复字符串。每个输入项都要保留一次，分组不能变成去重；组间顺序不影响答案。
解法：排序字符串作为哈希 key
核心思路
[!blue]
如果逐个拿新单词与已有单词比较，容易产生大量重复判断。可以先给每个单词生成一个只由字母组成决定、与原顺序无关的键，再用哈希表把键相同的单词放到同一列表。
排序就是一种这样的归一化方式。将单词复制到字符数组后排序，同种字母会聚在一起，各段长度保留了原来的出现次数。两个单词互为异位词时，排序结果必然相同；反过来，排序结果相同也意味着每个字母的数量一致，所以不会把不同类别混在一起。
哈希表的键使用排序后的字符串，值使用原单词列表。排序只作用于用于生成键的副本，加入答案的仍是原字符串，不能把所有单词都换成排序后的内容。
遍历时，键不存在就创建新组，存在就追加到原组。重复输入也执行追加，空串则以空字符串作为键。每个输入恰好进入一个由字母组成唯一确定的组，最后收集所有组即可。
解题步骤
- 建立从排序字符串到原单词列表的哈希表。
- 依次取出输入字符串，复制成字符数组并排序，转换成字符串键。
- 找到或创建该键对应的列表，把原字符串追加进去。
- 全部输入处理完后，返回哈希表中的所有列表，无需额外排序输出。
代码实现
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(1+k\log(k+1)))$，
n为字符串数，k为最大长度；包含每串的固定处理成本，空串也需要分组。- 空间复杂度：$O(n(k+1))$，保存签名、分组引用与排序副本，包含空串条目的存储。
关键点总结
[!green]
- 排序键与异位词关系双向等价，既不会拆散同类，也不会误合并不同类。
- 键负责判断类别，列表负责保存原始输入及其重复次数，两者用途不同。
- 空串也是合法类别，不需要从流程中单独剔除。
解法：字母频次作为哈希 key
核心思路
[!blue]
排序的目的只是抹去原字符顺序、保留每种字符出现次数。题目只含
26个小写字母，可以直接统计这些次数，省去排序。为每个字符串建立全零的
counts，其中counts[0]表示字母a的数量，直到counts[25]表示z的数量。逐字符累加后，两个字符串互为异位词，当且仅当这26个位置完全相同，所以整个频次数组就能充当分组键。键还要符合语言的比较规则。Java 的数组默认不按内容比较，这里通过
Arrays.toString(counts)生成带分隔的字符串，既保留各位置边界，也能按内容查表。Go 的[26]int是固定长度数组，可以按值比较，直接作为 map 的键即可，不能改成不可比较的切片。统计和分组过程仍然每个输入处理一次，列表保存原字符串及重复项。空字符串没有任何字母，对应全零计数，自然归入同一组。
解题步骤
- 创建分组哈希表。
- 对每个字符串创建全零的
26项计数，按字母下标逐个累加。- Java 将计数转换为带分隔的字符串键，Go 直接使用固定长度数组键。
- 将原字符串追加到对应组，最后收集并返回所有组。
代码实现
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String str : strs) {
int[] counts = new int[26];
for (int i = 0; i < str.length(); i++) {
counts[str.charAt(i) - 'a']++;
}
String key = Arrays.toString(counts);
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(str);
}
return new ArrayList<>(groups.values());
}
}
func groupAnagrams(strs []string) [][]string {
groups := make(map[[26]int][]string)
for _, str := range strs {
var counts [26]int
for i := 0; i < len(str); i++ {
counts[str[i]-'a']++
}
groups[counts] = append(groups[counts], str)
}
result := make([][]string, 0, len(groups))
for _, group := range groups {
result = append(result, group)
}
return result
}
复杂度分析
设有
n个字符串，最大长度为k，字母种类数C = 26。
- 时间复杂度：$O(n(k+C))$，逐字符统计，再处理固定长度的频次键；本题计数范围有限，Java 每项计数的文本长度也是常数。固定
C后可写成 $O(n(k+1))$。- 空间复杂度：$O(nC)$，最多保存
n个频次键和n个原字符串引用。固定字母表下为 $O(n)$，无需复制原单词内容。
关键点总结
[!green]
- 异位词的本质是每种字母的次数相等，频次键直接表达了这个条件。
- 每个计数位置必须保持独立，不能在编码时丢失边界。
- Java 需要按内容可比较的键，Go 的定长数组本身就支持值比较。
易错点总结
[!yellow]
- 把键加入结果而不是原字符串，会丢掉输入的字母排列。
- 用集合保存同组字符串，会把重复输入错误去重。
- 仅用长度、字母种类或字符编码之和作为键，不能完整描述各字母的出现次数。
- Java 数组默认按对象身份判断相等，不能直接把新建的
char[]或int[]作为按内容分组的键。- 将多位计数直接无分隔拼接，可能让不同频次数组得到相同字符串；键必须保留计数之间的边界。
- 忽略空串会丢失合法输入；排序法的空字符串键、计数法的全零键都能正常分组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 242. 有效的字母异位词 | 简单 | 分组键来自两串互为异位词的判定条件，本题需要把全部同类字符串聚合。 |
| 438. 找到字符串中所有字母异位词 | 中等 | 同样使用频次特征，原题在定长窗口中增量更新，本题对完整单词生成签名。 |