面试题 10.02 变位词组(Group Anagrams):排序哈希与计数哈希两种解法的 LeetCode 实战精讲
面试题 10.02 变位词组(Group Anagrams):排序哈希与计数哈希两种解法的 LeetCode 实战精讲
本篇技术指南围绕 doocs/leetcode 仓库中 《程序员面试金典(第 6 版)》系列 的「面试题 10.02 变位词组(Group Anagrams)」展开,完整讲解题目约束、暴力解法的性能瓶颈,以及「排序 + 哈希表」与「计数 + 哈希表」两种标准解法的时间复杂度推导与多语言实现,并结合仓库源码逐行印证实际写法。读完本文,你将掌握字母异位词分组问题的完整解题套路,能够在 Python、Java、C++、Go、TypeScript、Swift、Rust 等语言中独立实现,并理解两种解法各自的适用场景。
题目背景与问题定义
本题收录于《程序员面试金典(第 6 版)》第 10 章「排序与查找」,是面试中高频考察的字符串 + 哈希表综合题,题解文档位于 lcci/10.02.Group Anagrams/README.md。
题目要求编写一种方法,对字符串数组进行排序,将所有变位词组合在一起。所谓变位词(Anagram),是指字母相同、但排列不同的字符串,例如 "eat"、"tea"、"ate" 三者互为变位词。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明(题目约束):
- 所有输入均为小写字母;
- 不考虑答案输出的顺序。
与经典的 49. 字母异位词分组 相比,本题出自面试原书、题目表述稍有调整,但核心算法完全一致,仓库中两个题目的题解也保持同构,可以相互对照学习。
解题思路:从暴力两两比较到哈希分组
暴力解法的瓶颈
最直接的想法是两两比较字符串是否互为变位词:对每个字符串先排序,再与其余所有字符串比较。这种做法的复杂度约为 ,其中 是字符串个数, 是单个字符串的最大长度。
当词数较多时(例如 LeetCode 49 中 可达 ),平方级的比较次数会明显拖慢运行速度,显然不是面试中值得给出的答案。
核心洞察:排序后相同的串即为同一组
关键性质是:互为变位词的一组字符串,按照字符字典序排序后得到的是同一个字符串。例如:
"eat"、"tea"、"ate"排序后都是"aet";"tan"、"nat"排序后都是"ant";"bat"排序后是"abt"。
因此,把排序后的串当作哈希键(key),同一键下的原串自然成组,完全不需要两两比较。对每个字符串 计算 k = ''.join(sorted(s)) 并追加到 d[k],最后输出 d 的 value 列表即可——用一次 的排序换取一次哈希插入。
以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例,遍历结束时哈希表的状况如下:
| key | value |
|---|---|
"aet" |
["eat", "tea", "ate"] |
"ant" |
["tan", "nat"] |
"abt" |
["bat"] |
最后返回哈希表的 value 列表即可,顺序无关紧要(题目已明确不要求输出顺序)。
方法一:排序 + 哈希表
算法步骤清晰而固定,共三步:
- 遍历字符串,对每个字符串按照字符字典序排序,得到一个新的字符串;
- 以新字符串为
key,[str]为value,存入哈希表当中(典型结构为HashMap<String, List<String>>); - 后续遍历得到相同
key时,将其加入到对应的value当中。
时间复杂度:,其中 是字符串数组的长度, 是字符串的最大长度。
仓库源码实现
仓库中该方法对应的题解文件为 Solution.* 系列,下面逐一对照:
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) 省去了「键不存在则先初始化空列表」的判断;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());
}
}
Java 中字符串不可变,需要先 toCharArray() 转成字符数组排序,再 String.valueOf(t) 还原为字符串键;computeIfAbsent 是 JDK 8+ 的标准写法,等价于「键不存在则创建空列表」。
C++(Solution.cpp):
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;
}
};
先复制一份 k = s 再对其排序,避免破坏原串;emplace_back 直接构造避免拷贝;遍历哈希表时用结构化绑定 auto& [_, 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
}
Go 中字符串转为 []byte 后可用 sort.Slice 按字节排序,再转回字符串;命名返回值 (ans [][]string) 配合裸 return 使代码紧凑。
TypeScript(Solution.ts):
function groupAnagrams(strs: string[]): string[][] {
const d: Map<string, string[]> = new Map();
for (const s of strs) {
const k = s.split('').sort().join('');
if (!d.has(k)) {
d.set(k, []);
}
d.get(k)!.push(s);
}
return Array.from(d.values());
}
split('') 拆成字符数组、sort() 排序、join('') 还原字符串,三步串成一行;d.get(k)! 使用非空断言,因为上面刚 set 过。
Swift(Solution.swift):
class Solution {
func groupAnagrams(_ strs: [String]) -> [[String]] {
var d = [String: [String]]()
for s in strs {
let t = String(s.sorted())
d[t, default: []].append(s)
}
return Array(d.values)
}
}
Swift 字典下标访问支持 default: 参数,缺失键自动以空数组初始化,写法最简。
Rust(Solution.rs):
use std::collections::HashMap;
impl Solution {
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut map = HashMap::new();
for s in strs {
let key = {
let mut cs = s.chars().collect::<Vec<char>>();
cs.sort();
cs.iter().collect::<String>()
};
map.entry(key).or_insert(vec![]).push(s);
}
map.into_values().collect()
}
}
Rust 中 entry(key).or_insert(vec![]) 是「取或插」的惯用法,into_values() 直接消费哈希表得到所有分组。
方法二:计数 + 哈希表
排序键的缺点是引入了 的对数因子。而本题字符集很小——只有 26 个小写字母,因此可以把「排序」替换为「计数」,进一步降低单串处理成本。
具体做法:将每个字符串 中字符及其出现次数作为 key,将字符串 作为 value 存入哈希表。
时间复杂度:,其中 和 分别是字符串数组的长度和字符串的最大长度, 是字符集的大小,本题中 。每个词从 的排序变为 的线性扫描,分组语义不变。
仓库源码实现
该方法对应的题解文件为 Solution2.* 系列。
Python3(Solution2.py):
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())
长度为 26 的计数数组通过 ord(c) - ord('a') 映射到下标;tuple(cnt) 可哈希,直接作为字典键——这是 Python 特有的简洁优势。
Java(Solution2.java):
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 26; ++i) {
if (cnt[i] > 0) {
sb.append((char) ('a' + i)).append(cnt[i]);
}
}
String k = sb.toString();
d.computeIfAbsent(k, key -> new ArrayList<>()).add(s);
}
return new ArrayList<>(d.values());
}
}
Java 的 int[] 不能直接作 Map 键,因此将计数结果编码为规范化字符串:只保留出现次数 > 0 的字符,形如 "a2b1c5a3",同一组异位词编码后必然一致。
C++(Solution2.cpp):
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> d;
for (auto& s : strs) {
int cnt[26] = {0};
for (auto& c : s) ++cnt[c - 'a'];
string k;
for (int i = 0; i < 26; ++i) {
if (cnt[i]) {
k += 'a' + i;
k += to_string(cnt[i]);
}
}
d[k].emplace_back(s);
}
vector<vector<string>> ans;
for (auto& [_, v] : d) ans.emplace_back(v);
return ans;
}
};
与 Java 版同样的规范化编码思路,k += 'a' + i 与 k += to_string(cnt[i]) 交替拼接出键。
Go(Solution2.go):
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
}
Go 语言中定长数组 [26]int 天然可作 map 键(切片不行),直接以计数数组本身作为键,无需任何编码转换,是这版实现最优雅的地方。
两种方法对比与选型建议
| 维度 | 方法一:排序 + 哈希 | 方法二:计数 + 哈希 |
|---|---|---|
| 核心思想 | 排序后的字符串作为键 | 字符频次作为键 |
| 单串开销 | , | |
| 总体复杂度 | ||
| 键的形式 | 排序字符串(如 "aet") |
频次数组 / 编码串 |
| 额外空间 | 哈希表, | 每串一个长度 26 的计数, |
| 代码简洁度 | 各语言写法最统一 | 依赖语言对「数组作键」或元组的支持 |
选型建议:
- 若追求思路直观、各语言实现一致,选方法一,它是面试中最容易讲清楚的标准答案;
- 若字符集固定且很小(如本题 26 个小写字母)、字符串普遍较长,方法二在理论上更优;尤其 Go 语言可用
[26]int直接作键,Python 可用tuple(cnt),实现成本极低; - 需要注意:方法二依赖字符集可枚举。若输入可能包含任意 Unicode 字符,频次数组的规模将不可控,此时应回退到方法一。
两种方法的时间复杂度均已由题解文档给出并得到源码验证:方法一为 ,方法二为 ,。
仓库实现与延伸阅读
在 doocs/leetcode 仓库中,本题的完整素材如下,可供继续深入:
- 中文题解:lcci/10.02.Group Anagrams/README.md,英文题解:README_EN.md;
- 方法一源码:Python、Java、C++、Go、TypeScript、Swift、Rust(Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.swift、Solution.rs);
- 方法二源码:Python、Java、C++、Go(Solution2.py、Solution2.java、Solution2.cpp、Solution2.go);
- 同主题姊妹题:LeetCode 49. 字母异位词分组,在该目录下还可看到 C#、Rust 等更多语言版本以及 TypeScript 的计数实现(用
cnt.join(',')作键),可作为跨语言对照的补充案例。
总结
「变位词组」一题考察的核心是如何为「字母相同、排列不同」这一等价关系构造稳定的哈希键:
- 排序法:利用「变位词排序后相等」的性质,用排序串作键,单串 ;
- 计数法:利用「字符集有界(26 个小写字母)」的性质,用频次作键,单串 。
两种解法都能在 趟扫描内完成全部分组,空间复杂度均为 量级(哈希表总容量)。掌握「先构造规范形、再哈希分组」这一模式,不仅能 AC 本题与 LeetCode 49,还能迁移到「单词频次统计」「同义词合并」等一系列字符串分组问题中。