LeetCode LCR 033. 字母异位词分组
题目描述
题意分析
将每种字符出现次数完全相同的字符串分到一组。这里允许字符串内容完全相同，重复输入也要按出现次数保留，不能套用 LCR 032 排除相同字符串的条件。
每个字符串只含小写字母，也可能为空。结果顺序不限，因此只需找到可靠的分组依据，不必额外整理各组的输出顺序。
解法：排序签名分组
核心思路
[!blue]
与其逐对比较字符串，可以为每个字符串计算一个只由字符组成决定的签名。将字符排序后拼成字符串，就得到这样的签名：排序消除了原始顺序，但保留了每种字符的数量。
字符频次相同的两个串排序后一定相同；反过来，排序结果相同也说明每个字符的次数相同。这个双向关系保证同类不会被分开，不同类也不会混到一起。
用哈希表
d保存“签名 → 这一组的原字符串列表”。逐个计算签名，将原串追加到对应列表；没有这个签名时先建立空组。处理结束后，表中的每个列表就是一个完整分组。签名只作为分类键，返回值保留原字符串本身。重复字符串会被重复追加，空字符串的签名仍是空字符串，这些边界都不需要专门分支。
解题步骤
- 创建签名到字符串列表的哈希表。
- 对每个原串
s，复制字符并排序，再将排序结果转成签名k。Java 使用字符数组，Go 在小写字母约束下使用字节切片。- 若签名尚无分组，创建分组；随后追加原串
s，不能追加签名k。- 将哈希表的全部分组收集成结果，无需按签名或原串再排序。
代码实现
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());
}
}
import (
"sort"
)
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
}
复杂度分析
设字符串数为
n，最大字符串长度为L。
- 时间复杂度：$O(n(L\log(L+1)+1))$，每个字符串排序并构造签名，哈希键计算也需要读取签名；额外的常数项包含空字符串及收集分组的开销。
- 空间复杂度：$O(n(L+1))$，签名总长度最多为 $nL$，分组保存
n个原串引用；单次排序另需 $O(L)$ 的字符副本。
关键点总结
[!green]
- 排序后的签名完整保留字符频次，与原始排列顺序无关。
- 同组当且仅当签名相同，用哈希表即可一次遍历完成归组。
- 分类键是中间数据，组内保存原字符串及其每次出现。
易错点总结
[!yellow]
- 相同字符串属于同一组，不能因为内容一致就排除或去重。
- 返回的是原串，不是排序后的签名；应当排序字符副本，再把原串追加到组内。
- 字符集合相同不够，重复次数也必须相同，签名必须保留这些次数。
- 空字符串也有合法的空签名，应正常进入对应分组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 242. 有效的字母异位词 | 简单 | 分组键来自两串互为异位词的判定条件，本题需要把全部同类字符串聚合。 |
| 438. 找到字符串中所有字母异位词 | 中等 | 同样使用频次特征，原题在定长窗口中增量更新，本题对完整单词生成签名。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！