Python算法训练序列
数组与哈希 · Unit 04
← Unit 03
49
LeetCode 49Group Anagrams · 字母异位词分组
先给每个字符串生成“身份”，
再按身份放进同一个桶。
Unit 03 已经能判断两个字符串是否为异位词。Unit 04 不再逐对比较，而是为每个字符串生成一个稳定签名：同组字符串签名相同，不同组签名不同，然后用字典一次完成分组。
LeetCode #49 原题内容
中文转述 · 保留示例、约束与提交签名
题目要求
给定一个字符串数组 strs，把其中互为字母异位词的字符串分到同一组，并返回所有分组。输出分组及组内顺序均可以不同。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
# 在这里提交答案
约束
1 ≤ len(strs) ≤ 100000 ≤ len(strs[i]) ≤ 100strs[i]由小写英文字母组成。
示例
输入：["eat","tea","tan","ate","nat","bat"]
一种输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
一种输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
输入：[""]
输出：[[""]]
输出：[[""]]
输入：["a"]
输出：[["a"]]
输出：[["a"]]
1. 识别同组
2. 设计稳定签名
3. 签名作为字典键
4. 代码联动
5. 通用字符迁移
当前字符串的签名同组必须具有相同键
等待生成签名
groups：签名 → 字符串列表尚未分组
groups = {}
当前索引 i—
当前 word—
当前字符 ch—
当前 key—
桶数量0
补全 LeetCode 提交代码卡住可查看参考答案
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups =
for word in strs:
count =
for ch in word:
count[] += 1
key =
return
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
count = [0] * 26
for ch in word:
count[ord(ch) - ord("a")] += 1
key = tuple(count)
groups[key].append(word)
return list(groups.values())
为什么必须使用 tuple(count)？Python 字典键必须可哈希，而
list 可修改，不能作为字典键；tuple 不可变，可以稳定代表字符串的频次身份。排序版也正确：key = "".join(sorted(word))，但频次向量把每个单词的签名成本从 O(k log k) 降为 O(k)。代码—频次向量—分组字典联动示例：["eat","tea","tan","ate"]
1from collections import defaultdict
2class Solution:
3 def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
4 groups = defaultdict(list)
5 for word in strs:
6 count = [0] * 26
7 for ch in word:
8 count[ord(ch) - ord("a")] += 1
9 key = tuple(count)
10 groups[key].append(word)
11 return list(groups.values())
逐行播放，观察单词如何变成签名，并进入对应桶。
完成代码联动后进入通用字符迁移
补全正确、查看答案或播放完整轨迹后解锁。
迁移题：字符串不再只包含 a-z
若字符串包含中文、大小写或其他 Unicode 字符，固定26维数组不再适用。请改用可排序字符序列，或把 Counter(word) 转成稳定、可哈希的键。
本单元形成的算法Skill
当多个对象需要按“组成相同”分组时，不要进行两两比较。先把每个对象编译成稳定、可哈希的规范签名，再使用 signature → group 的字典完成一次扫描分组。
LeetCode #49规范化签名频次向量tuple可哈希defaultdict(list)时间 O(NK)
#217 哈希集合是否出现过
#1 哈希映射出现在哪里
#242 频次统计出现多少次
#49 当前：规范化分组怎样构造统一身份