LeetCode 49 题解:字母异位词分组(Group Anagrams)的哈希表与计数法详解
LeetCode 49 题解:字母异位词分组(Group Anagrams)的哈希表与计数法详解
本篇技术指南以 doocs/leetcode 仓库中 LeetCode 第 49 题「字母异位词分组(Group Anagrams)」的官方题解文档为核心,完整讲解该题的题目约束、两种主流解法(排序哈希表与计数键)的思路推导、复杂度分析与多语言实现,并结合仓库内的 Solution*.py、Solution*.java、Solution*.go 等源码文件印证每一段实现细节。读完本文,你将掌握"如何用一个规范化字符串作为分组键"这一通用技巧,并能独立写出 Python、Java、C++、Go、TypeScript、Rust、C# 任一语言的正确实现。
题目概述:什么是字母异位词分组
题目原文见 solution/0000-0099/0049.Group%20Anagrams/README_EN.md(中文版)。给定一个字符串数组 strs,需要将其中互为字母异位词(anagram)的字符串分到同一组,返回结果列表时不要求顺序。
字母异位词:字母相同、但排列不同的字符串。例如
"nat"与"tan"可以通过重新排列互相得到,因此它们属于同一组。
题目给出的三个示例:
- 示例 1:
strs = ["eat","tea","tan","ate","nat","bat"]输出[["bat"],["nat","tan"],["ate","eat","tea"]]。其中没有字符串能重新排列成"bat",所以"bat"单独成组;"nat"/"tan"互为异位词;"ate"/"eat"/"tea"互为异位词。 - 示例 2:
strs = [""],输出[[""]](空串单独成组)。 - 示例 3:
strs = ["a"],输出[["a"]](单字符串单独成组)。
约束条件(决定算法选择的硬性边界):
1 <= strs.length <= 10^4,字符串数组最多有 10000 个元素;0 <= strs[i].length <= 100,每个字符串最长 100 个字符;strs[i]仅由小写英文字母组成(这是方法二"计数键"能够成立的前提)。
方法一:哈希表 + 排序键
思路推导:为什么不能两两比较
文档的"Thinking"部分点出了最朴素的失败方案:两两判断是否互为异位词,即使先对每个串排序再比较,时间复杂度也是 。代入约束 、,平方级复杂度会明显超时,因此必须避免成对比较。
核心洞察是:一组异位词排序后得到的是同一个字符串,这个排序串天然可以作为该组的唯一标识(group id)。于是只需要:
- 遍历字符串数组,对每个字符串按字符字典序排序,得到规范化后的新字符串;
- 以该新字符串为
key、[str]为value存入哈希表(如HashMap<String, List<String>>); - 后续遍历遇到相同
key时,将原字符串追加到对应的value列表; - 最终返回哈希表所有
value组成的列表。
以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例,遍历结束时哈希表的状态为:
| key | value |
|---|---|
"aet" |
["eat", "tea", "ate"] |
"ant" |
["tan", "nat"] |
"abt" |
["bat"] |
可以看到 "eat"/"tea"/"ate" 排序后都是 "aet",因此自动聚到同一组;"tan"/"nat" 排序后都是 "ant";"bat" 排序后是唯一的 "abt",单独成组。
复杂度:时间 ,其中 为字符串数组长度, 为字符串最大长度(排序主导);空间 (哈希表存储所有字符串)。
仓库源码印证
仓库中该方法对应的可运行代码位于 solution/0000-0099/0049.Group%20Anagrams 目录下,命名规则为 Solution.<ext>:
- Python3(Solution.py):
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
k = ''.join(sorted(s))
d[k].append(s)
return list(d.values())
defaultdict(list) 省去了"先判断 key 是否存在"的分支,sorted(s) 返回字符列表,''.join(...) 拼回排序串作为键。
- Java(Solution.java):
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);
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}
这里用 computeIfAbsent 实现"无则建列表、有则追加"的原子操作;注意排序对象是 char[],最后用 String.valueOf(t) 转回字符串。
- C++:
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> d;
for (auto& s : strs) {
string k = s;
sort(k.begin(), k.end());
d[k].emplace_back(s);
}
vector<vector<string>> ans;
for (auto& [_, v] : d) ans.emplace_back(v);
return ans;
}
};
直接拷贝原串再 sort,unordered_map 用哈希实现 平均查找;结构化绑定 [_, v] 遍历收集结果。
- Go(Solution.go):
func groupAnagrams(strs []string) (ans [][]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)
d[k] = append(d[k], s)
}
for _, v := range d {
ans = append(ans, v)
}
return
}
- TypeScript:
s.split('').sort().join('')一步得到排序键,Map<string, string[]>配合d.get(k)!.push(s)追加。 - Rust:
t.sort_unstable()对Vec<char>原地排序,d.entry(k).or_insert_with(Vec::new).push(s)是 Rust 惯用的 entry API。 - C#:
Array.Sort(t)排序字符数组,new string(t)转回字符串,d.ContainsKey判断后追加。
完整的七语言实现都可在仓库目录 solution/0000-0099/0049.Group%20Anagrams 中查看,每个文件都是可直接提交到 LeetCode 的完整 Solution 类/函数。
方法二:计数键(Counting)
思路推导:省掉排序的对数因子
文档的"Thinking"部分指出方法一的局限:对每个串排序是 ,但本题字符集只有 26 个小写字母,且 ,排序中的 因子其实是"浪费"。
更便宜的键来自计数:统计字符串中每个字母出现的次数,用这组计数作为分组键。因为互为异位词的两个字符串,其 26 个字母的计数完全相同;反之计数相同则必然互为异位词。哈希分组框架不变,只是把"排序键"换成"计数键",单串处理降为线性:
- 对每个字符串
s,统计 26 个小写字母各出现多少次; - 将计数结果(如长度为 26 的数组/元组,或拼接成的字符串)作为
key,字符串s作为value存入哈希表; - 遍历结束后返回哈希表的所有
value。
复杂度:时间 ,其中 、 分别为数组长度和最大串长, 为字符集大小(本题 )。相比方法一,去掉了 因子;空间复杂度仍为 。
各语言如何构造"计数键"
不同语言对"数组能否直接做 Map 键"的支持不同,仓库源码展示了四种构造策略(对应 Solution2.
- Python3(Solution2.py):直接把
list转成tuple作为键(元组可哈希):
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
cnt = [0] * 26
for c in s:
cnt[ord(c) - ord('a')] += 1
d[tuple(cnt)].append(s)
return list(d.values())
- Go(Solution2.go):Go 的数组类型
[26]int天然可作为 map 键(切片不行),因此直接d[cnt] = append(d[cnt], s),最简洁:
func groupAnagrams(strs []string) (ans [][]string) {
d := map[[26]int][]string{}
for _, s := range strs {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
d[cnt] = append(d[cnt], s)
}
for _, v := range d {
ans = append(ans, v)
}
return
}
- Rust:
[i32; 26]数组实现了Hash/Eq,同样直接d.entry(cnt).or_insert_with(Vec::new).push(s)。 - Java / C++ / TypeScript / C#:由于数组不能直接做键,需要把计数序列序列化成字符串:
- Java:遍历 26 个位置,仅当
cnt[i] > 0时拼接(char)('a' + i) + cnt[i],例如"a1e3"这种紧凑形式; - C++:同样拼接
'a' + i与to_string(cnt[i]); - TypeScript / C#:直接
cnt.join(',')/string.Join(",", cnt),用逗号分隔的完整计数串作键(注意:这种写法会把 26 个计数全部拼出,包含大量 0,键更长但实现最简单)。
- Java:遍历 26 个位置,仅当
需要提醒的边界细节:紧凑拼接必须包含字符本身(如 Java 的 'a'+i 前缀),否则 "ab" 与 "aab" 会分别产生 "11" 与 "21"——由于数字拼接 1、2、1 可能产生歧义("1"+"1" 与 "11"),因此仓库实现统一采用"字母 + 次数"的成对格式,保证键无歧义;而 Go/Rust 直接用可哈希数组则完全规避了序列化问题。
两种方法对比与选型建议
| 对比维度 | 方法一:排序键 | 方法二:计数键 |
|---|---|---|
| 键的构造 | 排序后字符串 | 26 维计数(元组/数组/序列化串) |
| 单串处理耗时 | , | |
| 总时间复杂度 | ||
| 空间复杂度 | ||
| 适用前提 | 任意字符集 | 字符集有限且已知(本题 26 个小写字母) |
| 实现难度 | 低,代码最短 | 低,但需处理"数组如何做键"的语言差异 |
选型结论:
- 若字符集有限且固定(本题就是 26 个小写字母),方法二在理论上更优,尤其适合
k较大、串多的场景; - 若字符集未知、包含 Unicode 或数字符号等,排序键更具通用性,实现也最不易出错;
- 两种方法都只需一趟遍历 + 一次哈希聚合,不存在两两比较,因此都能在 的约束下轻松通过。
仓库中的关联变体与延伸学习
异位词分组是字符串哈希分组的经典范式,该思想在仓库其他模块中同样出现:
- 程序员面试金典版:同一题目以「面试题 10.02. 变位词组」的形式收录在 lcci/10.02.Group Anagrams/README.md,题解思路与本题完全一致,可以对照阅读多版本实现(该目录同样提供了
Solution2.*计数版)。 - 同源技巧:"将无序信息规范化为唯一标识"的哈希键思想,在仓库的 字母异位词类题目 与字符串计数类题目中反复出现,适合作为一类题统一训练。
如果你想直接运行或复现,仓库中每个题解目录都提供了可直接提交的源码文件,例如 Python 版 Solution.py 与计数版 Solution2.py,其余 Java/C++/Go/TS/Rust/C# 版本同理。
小结
本文围绕 LeetCode 49. Group Anagrams 的官方题解,讲清了两个核心知识点:
- 用规范化字符串做分组键:异位词排序后相同,排序串即组 id,一趟哈希即可完成分组,避免 两两比较;
- 用计数做更廉价的键:在字符集固定(26 个小写字母)的前提下,把排序的 降为线性的 ,并通过 Python 元组、Go 数组、Rust 数组或 Java/C++ 的序列化字符串等不同方式落地。
同时结合 doocs/leetcode 仓库中七种语言的 Solution.* 与 Solution2.* 源码,逐一印证了每种实现的关键细节。掌握"排序键 / 计数键 + 哈希聚合"这一模式后,面对大规模字符串分类问题,你将能第一时间写出高效且不易出错的解法。