Leetcode hot100 字母异位词分组
题目：给你一个字符串数组，将字母异位词（字母相同、排列不同的单词，如 `eat` 与 `tea`）组合在一起，返回分组结果。分组内顺序任意，输出顺序任意。
思路：互为异位词的单词，其字符重排后相同。据此可以为每个单词构造一个"规范键"（排序后的字符串，或 26 个字母的计数），将键相同的单词归入同一组，用哈希表完成分组。
### Python
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())
```
逐行解释：
| 行 | 代码 | 解释 |
|---|---|---|
| 3 | `groups = defaultdict(list)` | 哈希表，键为异位词的规范键，值为同组单词列表。`defaultdict(list)` 在访问不存在的键时自动创建空列表，省去键是否存在的判断 |
| 4 | `for s in strs:` | 遍历每个单词 |
| 5 | `key = ''.join(sorted(s))` | `sorted(s)` 将字符排序，`''.join(...)` 拼回字符串。排序结果相同者互为异位词 |
| 6 | `groups[key].append(s)` | 将单词追加到对应分组；键首次出现时自动建组 |
| 7 | `return list(groups.values())` | 取出全部分组，转为列表返回 |
### C++
```cpp
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>> res;
for (auto& [key, group] : groups) {
res.push_back(group);
}
return res;
}
};
```
逐行解释：
| 行 | 代码 | 解释 |
|---|---|---|
| 4 | `unordered_map<string, vector<string>> groups;` | 哈希表：键为排序后的字符串，值为同组单词。基于哈希实现，单次操作平均 O(1) |
| 5 | `for (const string& s : strs)` | 范围 for 遍历，常量引用避免拷贝 |
| 6 | `string key = s;` | 拷贝一份用于排序，不能排序原单词（其为 const，且原数据仍需保留） |
| 7 | `sort(key.begin(), key.end());` | 原地按字典序排序，如 `"eat"` → `"aet"` |
| 8 | `groups[key].push_back(s);` | 键不存在时 `operator[]` 自动默认构造空桶，再执行 `push_back` |
| 10 | `vector<vector<string>> res;` | 结果数组 |
| 11 | `for (auto& [key, group] : groups)` | C++17 结构化绑定遍历键值对，`group` 即某一组 |
| 12 | `res.push_back(group);` | 逐组加入结果。C++ 不像 Python 可直接取 `values()`，须手动遍历拼装 |
## 解法二：字符计数作为键（避免排序）
### Python
```python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
```
关键行解释：
| 行 | 代码 | 解释 |
|---|---|---|
| 5 | `count = [0] * 26` | 长度 26 的计数数组，对应 a~z 出现次数 |
| 7 | `count[ord(c) - ord('a')] += 1` | `ord(c) - ord('a')` 将字符映射为 0~25 下标，计数加一 |
| 8 | `groups[tuple(count)].append(s)` | 列表不可哈希，须转元组作为键；同组异位词计数元组相同 |
### C++
```cpp
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 自定义哈希函数：将 26 个计数映射为一个 size_t
auto arrayHash = [fn = hash<int>{}](const array<int, 26>& a) -> size_t {
return accumulate(a.begin(), a.end(), 0ull,
[&](size_t acc, int x) { return (acc << 1) ^ fn(x); });
};
unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> groups(0, arrayHash);
for (const string& s : strs) {
array<int, 26> count{};
for (char c : s) {
count[c - 'a']++;
}
groups[count].push_back(s);
}
vector<vector<string>> res;
for (auto& [key, group] : groups) {
res.push_back(group);
}
return res;
}
};
```
关键行解释：
| 行 | 代码 | 解释 |
|---|---|---|
| 5 | `auto arrayHash = [fn = hash<int>{}](const array<int, 26>& a) -> size_t` | C++ 的 `array<int, 26>` 无默认哈希，须自定义。lambda 以初始化捕获引入标准库的 int 哈希器 `fn` |
| 6 | `return accumulate(...)` | 对 26 个计数逐项混合：`(acc << 1) ^ fn(x)` 是常见哈希合并手法，使不同计数组合尽量映射到不同值 |
| 10 | `unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> groups(0, arrayHash);` | 键类型为计数数组，第三模板参数指定哈希器，构造时传入 |
| 14 | `array<int, 26> count{};` | `{}` 保证 26 个元素全部初始化为 0 |
| 16 | `count[c - 'a']++;` | 字符映射为下标，计数加一 |
| 18 | `groups[count].push_back(s);` | `array` 支持逐元素 `==` 比较，计数相同者归入同组 |
## 复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 排序键 | O(n·k log k) | O(n·k) | n 为单词数，k 为单词最大长度；每词排序耗时 k log k |
| 计数键 | O(n·k) | O(n·k) | 省去排序的 log 因子 |
结论：计数法理论复杂度更优，排序法键为短字符串、实现简洁。词长较短时二者实际差距很小，面试可先写排序法，口头补充计数法作为优化；若面试官明确要求避免排序，再给出计数法实现。
#LeetCode#哈希表#字符串