LeetCode 49 题解:字母异位词分组(Group Anagrams)的哈希表与计数法详解

原创2026-10-15 23:51:111,738 阅读
文章标签:教程示例工程教育

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"部分点出了最朴素的失败方案:两两判断是否互为异位词,即使先对每个串排序再比较,时间复杂度也是 O(n2⋅klog⁡k)O(n^2 \cdot k \log k)。代入约束 n≤104n \le 10^4、k≤100k \le 100,平方级复杂度会明显超时,因此必须避免成对比较。

核心洞察是:一组异位词排序后得到的是同一个字符串,这个排序串天然可以作为该组的唯一标识(group id)。于是只需要:

  1. 遍历字符串数组,对每个字符串按字符字典序排序,得到规范化后的新字符串;
  2. 以该新字符串为 key、[str] 为 value 存入哈希表(如 HashMap<String, List<String>>);
  3. 后续遍历遇到相同 key 时,将原字符串追加到对应的 value 列表;
  4. 最终返回哈希表所有 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",单独成组。

复杂度:时间 O(n×k×log⁡k)O(n \times k \times \log k),其中 nn 为字符串数组长度,kk 为字符串最大长度(排序主导);空间 O(n×k)O(n \times k)(哈希表存储所有字符串)。

仓库源码印证

仓库中该方法对应的可运行代码位于 solution/0000-0099/0049.Group%20Anagrams 目录下,命名规则为 Solution.<ext>:

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(...) 拼回排序串作为键。

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 用哈希实现 O(1)O(1) 平均查找;结构化绑定 [_, v] 遍历收集结果。

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"部分指出方法一的局限:对每个串排序是 O(klog⁡k)O(k \log k),但本题字符集只有 26 个小写字母,且 k≤100k \le 100,排序中的 log⁡k\log k 因子其实是"浪费"。

更便宜的键来自计数:统计字符串中每个字母出现的次数,用这组计数作为分组键。因为互为异位词的两个字符串,其 26 个字母的计数完全相同;反之计数相同则必然互为异位词。哈希分组框架不变,只是把"排序键"换成"计数键",单串处理降为线性:

  1. 对每个字符串 s,统计 26 个小写字母各出现多少次;
  2. 将计数结果(如长度为 26 的数组/元组,或拼接成的字符串)作为 key,字符串 s 作为 value 存入哈希表;
  3. 遍历结束后返回哈希表的所有 value。

复杂度:时间 O(n×(k+C))O(n \times (k + C)),其中 nn、kk 分别为数组长度和最大串长,CC 为字符集大小(本题 C=26C = 26)。相比方法一,去掉了 log⁡k\log k 因子;空间复杂度仍为 O(n×k)O(n \times k)。

各语言如何构造"计数键"

不同语言对"数组能否直接做 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 的 'a'+i 前缀),否则 "ab" 与 "aab" 会分别产生 "11" 与 "21"——由于数字拼接 1、2、1 可能产生歧义("1"+"1" 与 "11"),因此仓库实现统一采用"字母 + 次数"的成对格式,保证键无歧义;而 Go/Rust 直接用可哈希数组则完全规避了序列化问题。

两种方法对比与选型建议

对比维度 方法一:排序键 方法二:计数键
键的构造 排序后字符串 26 维计数(元组/数组/序列化串)
单串处理耗时 O(klog⁡k)O(k \log k) O(k+C)O(k + C),C=26C = 26
总时间复杂度 O(n×k×log⁡k)O(n \times k \times \log k) O(n×(k+C))O(n \times (k + C))
空间复杂度 O(n×k)O(n \times k) O(n×k)O(n \times k)
适用前提 任意字符集 字符集有限且已知(本题 26 个小写字母)
实现难度 低,代码最短 低,但需处理"数组如何做键"的语言差异

选型结论:

  • 若字符集有限且固定(本题就是 26 个小写字母),方法二在理论上更优,尤其适合 k 较大、串多的场景;
  • 若字符集未知、包含 Unicode 或数字符号等,排序键更具通用性,实现也最不易出错;
  • 两种方法都只需一趟遍历 + 一次哈希聚合,不存在两两比较,因此都能在 n=104n = 10^4 的约束下轻松通过。

仓库中的关联变体与延伸学习

异位词分组是字符串哈希分组的经典范式,该思想在仓库其他模块中同样出现:

  • 程序员面试金典版:同一题目以「面试题 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 的官方题解,讲清了两个核心知识点:

  1. 用规范化字符串做分组键:异位词排序后相同,排序串即组 id,一趟哈希即可完成分组,避免 O(n2)O(n^2) 两两比较;
  2. 用计数做更廉价的键:在字符集固定(26 个小写字母)的前提下,把排序的 O(klog⁡k)O(k \log k) 降为线性的 O(k+C)O(k + C),并通过 Python 元组、Go 数组、Rust 数组或 Java/C++ 的序列化字符串等不同方式落地。

同时结合 doocs/leetcode 仓库中七种语言的 Solution.* 与 Solution2.* 源码,逐一印证了每种实现的关键细节。掌握"排序键 / 计数键 + 哈希聚合"这一模式后,面对大规模字符串分类问题,你将能第一时间写出高效且不易出错的解法。

登录后查看全文
leetcode