KingOfEgg

题目：给你一个字符串数组，将字母异位词（字母相同、排列不同的单词，如 eat 与 tea）组合在一起，返回分组结果。分组内顺序任意，输出顺序任意。

思路：互为异位词的单词，其字符重排后相同。据此可以为每个单词构造一个"规范键"（排序后的字符串，或 26 个字母的计数），将键相同的单词归入同一组，用哈希表完成分组。

解法一：排序作为键

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++

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

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++

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 因子

结论：计数法理论复杂度更优，排序法键为短字符串、实现简洁。词长较短时二者实际差距很小，面试可先写排序法，口头补充计数法作为优化；若面试官明确要求避免排序，再给出计数法实现。