字母异位词分组
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。通常，所有源单词中的字母恰好只使用一次。
示例 1
"nat" 与 "tan" 互为异位词；"ate"、"eat"、"tea" 互为异位词；"bat" 单独成组。示例 2
示例 3
模拟答题者思考
1. 最直接：对每个字符串，和其余所有串两两比较是否为异位词（排序后相等或字符频次相同），相同则划入同一组——思路正确，但最坏要 O(n²) 次比较，每次比较还要 O(k log k) 排序。
2. 重复在哪里？判断「eat 和 tea 是否同组」时，其实不必关心它们具体怎么排列，只关心字母 multiset 是否相同——也就是说，异位词共享同一个「签名」。
3. 关键转化：为每个字符串算一个签名 key（排序后的串，如 "tan" → "ant"），用哈希表 groups[key] 收集所有同签名字符串；扫一遍输入即可完成分组。
4. 手推示例 1："eat","tea","ate" 的 key 都是 "aet"，落入同一列表；"tan","nat" 的 key 都是 "ant"；"bat" 的 key 是 "abt"，单独一组。
5. 另一种等价签名是长度 26 的字符计数元组（O(k) 不需排序），但排序写法更短；n ≤ 10⁴, k ≤ 100，总复杂度 O(n · k log k) 完全够用。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
groups | dict[str, list[str]] | 定义：从「异位词签名」到「同组字符串列表」的哈希表，最终答案即其所有 value 维护：遍历过程中，同一签名下的字符串始终被放在同一个列表里 更新：每处理一个 s，计算签名 key，执行 groups.setdefault(key, []).append(s) |
s | str | 定义：当前正在处理的输入字符串 维护：外层循环每次取 strs 中的一个元素，内层只读不改原串更新：按输入顺序逐个推进，直到全部处理完 |
key | str | 定义：字符串 s 的异位词签名，取排序后的结果（如 "eat" → "aet"）维护：互为异位词的字符串必然得到相同的 key，不同组则 key 不同更新：对每个 s 重新计算：key = "".join(sorted(s)) |
strs | list[str] | 定义：输入字符串数组，长度 n，每个串长度不超过 100维护：只读遍历，不修改元素内容 更新：作为外层循环的数据源，驱动整次分组 |
落码步骤
1. 初始化空哈希表 groups = {}
2. 遍历每个字符串 s in strs
3. 计算签名 key = "".join(sorted(s))
4. 若 key 不在表中则 groups[key] = []，然后将 s 追加到 groups[key]
5. 返回 list(groups.values())（外层列表顺序任意）
代码实现
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups: dict[str, list[str]] = {}
for s in strs:
key = "".join(sorted(s))
if key not in groups:
groups[key] = []
groups[key].append(s)
return list(groups.values())class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (const string& s : strs) {
string key = s;
sort(key.begin(), key.end());
groups[key].push_back(s);
}
vector<vector<string>> ans;
for (auto& [k, v] : groups) {
ans.push_back(move(v));
}
return ans;
}
};
// 时间 O(n·k log k)，空间 O(n·k)复杂度分析
O(n · k log k)
O(n · k)
常见坑
不能用「字符串长度」当 key——"ab" 和 "cd" 长度相同但不是异位词，必须比较字母组成（排序或计数）。
返回的是「分组列表的列表」，外层顺序任意，但每组内的字符串必须来自输入、不能遗漏或重复。
空字符串 "" 排序后仍是 ""，应正常入组；不要当作特殊值跳过。
必测边界 Case
strs = ["a"] → [["a"]]
strs = [""] → [[""]]
strs = ["abc","bca","cab"] → [["abc","bca","cab"]]（只有一个分组）
strs = ["a","b","c"] → [["a"],["b"],["c"]]（每组仅一个元素）
strs = ["dd","dd"] → [["dd","dd"]]（相同签名，应归入同一组）