49. 字母异位词分组 (Medium)
专题归类： 01-哈希表 · 03-数组 LeetCode 链接： https://leetcode.cn/problems/group-anagrams/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给你一个字符串数组，请你将字母异位词组合在一起。字母异位词指字母相同但排列不同的字符串。
示例：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
补充说明：
- 字符串数组长度范围：
1 <= strs.length <= 10^4 - 字符串长度范围：
0 <= strs[i].length <= 100 - 所有字符串仅包含小写英文字母
- 可以按任意顺序返回结果
题目详细分析
数据范围含义：
- 数组最多 10^4 个字符串，每个字符串最长 100 个字符。暴力两两比较（比较每个字符串的每个字符）会达到 O(n^2 × k)，显然不可行。
- 仅包含小写英文字母（26 个），这个限制非常关键——它意味着我们可以用固定大小的计数数组来表征一个字符串，而不必依赖排序。
- 字符串可能为空串（长度为 0），空串的字母异位词分组就是它自己。
输入输出特征：
- 输入是字符串数组，输出是二维字符串数组（分组列表）。
- 输出顺序不限，这意味着不需要考虑分组之间的顺序。
- 同一个分组内的字符串互为字母异位词。
核心约束：
- 如何定义”同一组”？本质是找到一种映射方式 f(str)，使得 f(str1) == f(str2) 当且仅当 str1 和 str2 互为字母异位词。
- 这个映射 f 必须充要（不能把不同的组映射到一起）。
隐藏条件：
- 分组操作天然需要哈希表：key 是”组标识”，value 是组内字符串列表。
- 字母异位词分组的难点在于设计 key，而不是分组本身。
小白版直白理解
想象你要整理一堆单词卡片。你发现有些单词虽然字母顺序不一样，但用的字母完全相同——比如”ate”（吃）和”eat”（吃），还有”tea”（茶），它们都用了 a、e、t 这三个字母。
笨办法： 拿每张卡片去和其他所有卡片比，看字母是不是一样。卡片多了就累死了。
聪明办法： 你发现每次把单词的字母按顺序排好（“ate” -> “aet”, “eat” -> “aet”, “tea” -> “aet”），就能得到一个”单词指纹”。指纹相同的卡片就扔到一个盒子里。
更快的办法（计数指纹）： 排序也挺花时间。你还可以做个更精细的指纹——数一下每个字母出现了几次。比如 “ate” 是 “a:1, e:1, t:1”，这个指纹同样能标识一组字母异位词，而且不需要排序。
解题思路
思路一：排序法（推荐，简洁易懂）
核心想法： 互为字母异位词的两个字符串，排序后的结果完全相同。
为什么这样想： 字母异位词的本质是”字符的多重集相同”。排序后，多重集变成了确定的字符串，可以作为哈希表的 key。
遍历每个字符串，将其排序后的结果作为 key，原字符串追加到对应的列表中。
from collections import defaultdict
def groupAnagrams(strs):
"""
排序法：key = 排序后的字符串
"""
groups = defaultdict(list)
for s in strs:
# 排序后的字符串作为分组标识
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())时间复杂度： O(n × k log k)，其中 n 是字符串数量，k 是字符串最大长度 空间复杂度： O(n × k)
思路二：计数法（长字符串时更高效）
核心想法： 用长度为 26 的数组统计每个字符出现次数，将计数元组作为 key。
关键洞察： 对于非常长的字符串，排序 O(k log k) 的开销较大。而计数法只需要 O(k) 遍历一次字符串即可。但计数数组转为元组后占用的空间比排序字符串大（26 个整数的元组 vs 排序后的 k 个字符）。
from collections import defaultdict
def groupAnagrams(strs):
"""
计数法：key = 字符计数的元组
适合字符串很长（k很大）的场景
"""
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for ch in s:
count[ord(ch) - ord('a')] += 1
# 列表不可哈希，转为元组作为 key
groups[tuple(count)].append(s)
return list(groups.values())时间复杂度： O(n × k)，避免排序的 O(k log k) 空间复杂度： O(n × k)，但每个 key 固定占用 26 个整数空间
思路三：质数映射法（巧妙但有限制）
核心想法： 每个字母对应一个质数，字符串的”哈希值”是所有字母对应质数的乘积。
关键洞察： 质数乘积具有唯一分解性——不同的字母组合乘积一定不同（乘法交换律确保字母顺序不影响结果）。这个方法从理论上非常巧妙。
但实际应用有大数溢出风险——对于长字符串，乘积会变得极大，Python 虽然支持大整数，但计算和存储开销都会增大。
from collections import defaultdict
def groupAnagrams(strs):
"""
质数映射法：每个字母映射到一个质数，乘积作为 key
"""
primes = {
'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13,
'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37,
'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61,
's': 67, 't': 71, 'u': 73, 'v': 79, 'w': 83, 'x': 89,
'y': 97, 'z': 101
}
groups = defaultdict(list)
for s in strs:
key = 1
for ch in s:
key *= primes[ch]
groups[key].append(s)
return list(groups.values())时间复杂度： O(n × k) 空间复杂度： O(n × k)，但 key 是整数，比元组更省空间 注意： 字符串较长时乘积可能极大，导致性能下降
易错点
- 哈希 key 必须可哈希： Python 中列表不能作为字典的 key（list 不可哈希）。计数法必须将
list转为tuple。 - 计数数组维度： 题目限定小写字母，数组长度是 26。如果字符集扩展（如包含大写字母），数组长度需要调整。
- 空字符串处理： 空字符串
""排序后还是""，计数数组全为 0，这两种方法都能正确处理空串。 - 性能选择： 排序法在 k 较小（k <= 100）时非常高效且代码简洁，是面试中最推荐的方法。计数法和质数法虽然理论更优，但实际差异不大。
- 质数溢出： 质数乘积增长极快，对于 k=100 的字符串，乘积可以达到天文数字，虽不会溢出但会变慢。
框架提炼
哈希表分组模板：
核心套路是设计一个”分组标识函数”f(x)，使得同一组的元素 f(x) 值相同，不同组的元素 f(x) 值不同。
from collections import defaultdict
def group_items(items):
"""
通用分组模板
"""
groups = defaultdict(list)
for item in items:
key = compute_group_key(item) # 设计分组标识函数
groups[key].append(item)
return list(groups.values())分组标识函数的设计原则：
- 同一组必须映射到相同 key（一致性）
- 不同组必须映射到不同 key（区分度）
- key 必须是可哈希的（Python dict 的要求）
字母异位词分组问题中，三种设计思路：
| 方法 | 分组标识函数 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| 排序法 | sorted(s) | O(k log k) | 短字符串，代码最简洁 |
| 计数法 | tuple(count) | O(k) | 长字符串，理论更优 |
| 质数法 | product(primes[c]) | O(k) | 追求极致速度，注意溢出 |
关联题目
- 242-有效的字母异位词 — 本题的简化版，判断两个字符串是否为字母异位词，本质就是比较两个字符串的”指纹”是否相同
- 1-两数之和 — 同样使用哈希表，但用途是”查找”而非”分组”，体现了哈希表的两大核心应用场景
- 128-最长连续序列 — 同样是哈希表 + 数组，但用哈希集合去重后找连续序列，体现了哈希表”去重后快速查找”的能力