题目描述
把字母异位词(含相同字母、只是顺序不同的词)分到同一组，返回所有分组。
思路解析
最直接的想法：拿每个词去和已有的每一组比，判断是不是异位词。可这样每比一对都要排序一次，n 个词两两比是 O(n²) 级，重复排序太多。
转折：异位词排序后完全一样，所以把「排序后的字符串」当 key。建哈希表 key → 词列表，遍历时算出 key 就往对应桶里塞，同 key 自动相遇，不用两两比较，只扫一遍。
开始扫描 · 哈希表为空：准备一个空哈希表 mp(key → 词列表)。从第一个词 eat 开始，依次给每个词算 key、归桶。
处理 "eat" · key 不存在 → 新建桶："eat" 排序后 = "aet"。哈希表里还没有这个 key，新建一个桶，放入 eat。这是「新 key」分支。
处理 "tea" · key 已存在 → 归入："tea" 排序也是 "aet"，key 已存在，直接塞进同一个桶——这就是「已存在 key」分支，和上一步对比着看。
处理 "tan" · 新 key → 新建第 2 桶："tan" 排序 = "ant"，是个从没见过的 key，新建第二个桶放入 tan。
处理 "ate" · 回到第 1 桶："ate" 排序 = "aet"，又命中第一个桶，归入。注意它和 eat、tea 隔了两个词才出现，但靠统一 key 照样聚到一起。
处理 "nat" · 归入第 2 桶："nat" 排序 = "ant"，key 已存在，进第二个桶，和 tan 作伴。
处理 "bat" · 新 key → 新建第 3 桶："bat" 排序 = "abt"，新 key，新建第三个桶。注意它只比 ant 多了字母 b，排序后就完全不同，所以不会和 tan/nat 混。
扫描完毕 · 取出所有桶：六个词只扫了一遍，每个词算一次 key 就归位。把所有桶的列表取出来就是答案：[[eat,tea,ate], [tan,nat], [bat]] 共 3 组。
分组 / 去重这类题，核心就是想出一个「同类元素算出来一样」的归一化 key，剩下交给哈希表自动聚合。
参考代码（Python）
1mp = collections.defaultdict(list)
2for s in strs:
3 key = class="cl-str">"".join(sorted(s)) # 排序后的串当 key
4 mp[key].append(s) # 塞进对应桶(不存在自动建)
5return list(mp.values())复杂度分析
- 时间复杂度：O(n·k·logk) —— n 个词，每个词排序需 k·logk(k 为词长)
- 空间复杂度：O(n·k) —— 哈希表存下全部 n 个词，每个长 k
套路模板
记住骨架：想一个「同类→同 key」的归一化函数，用 defaultdict 自动建桶。key 两种写法：排序(简单)或 26 字母计数元组(更快)；其它分组题只换 key 算法。
1# 「把同类元素分组 / 去重」都套这个骨架
2from collections import defaultdict
3groups = defaultdict(list)
4for s in strs:
5 key = class="cl-str">"".join(sorted(s)) # 法1: 排序当 key O(klogk)
6 # cnt=[0]*26; for c in s: cnt[ord(c)-97]+=1; key=tuple(cnt) # 法2: 字母计数 O(k) 更快
7 groups[key].append(s) # 塞进同一个桶
8return list(groups.values())易错点
- 错误写法：直接拿原字符串 s 当 key → 正确写法：用 sorted(s) 或 26 字母计数元组当 key（异位词原串本就不同(eat≠tea)，必须归一化后才会算出同一个 key）
- 错误写法：用 [0]*26 这个 list 直接当 dict 的 key → 正确写法：用 tuple(cnt) 元组当 key（list 不可哈希，当 key 会 TypeError；元组才能哈希）
- 错误写法：普通 dict 不判存在就 mp[key].append → 正确写法：用 defaultdict(list) 或先判 key 再建（普通 dict 里 key 不存在时直接 append 会 KeyError）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。