49. 字母异位词分组

题目描述

把字母异位词(含相同字母、顺序不同)分到同一组。

思路解析

异位词排序后完全一样，所以把「排序后的字符串」当 key。用哈希表 key → 词列表，遍历时按 key 往对应桶里塞。

处理 "eat"："eat" 排序后 = "aet"，哈希表里没有这个 key，新建一个桶，放入 eat。

处理 "tea"："tea" 排序也是 "aet"，key 已存在，直接塞进同一个桶。

处理 "tan"："tan" 排序 = "ant"，新 key，新建第二个桶。

处理 "ate"："ate" 排序 = "aet"，回到第一个桶。

处理 "nat"："nat" 排序 = "ant"，进第二个桶。

处理 "bat"："bat" 排序 = "abt"，新 key，新建第三个桶。

结果：遍历完毕，把所有桶的列表取出来就是答案：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
• 空间复杂度：O(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())

易错点

• ❌ 用原字符串当 key → ✅ 用 sorted 后或字母计数当 key（异位词原串不同，必须归一化）
• ❌ 普通 dict 不判存在就 append → ✅ 用 defaultdict(list) 或先判 key（否则 key 不存在会报错）

以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。