49. 字母异位词分组

难度：🟡 Medium | 标签：哈希、字符串、排序 | 状态：⬜ LeetCode 链接

思路

异位词的不变量 = 字母组成。排序后的字符串作为 key 即可分组。

也可用「计数数组转字符串」当 key，避免排序的 O(k log k)，但代码更繁。面试默认用排序版。

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            mp[key].push_back(s);
        }
        vector<vector<string>> res;
        res.reserve(mp.size());
        for (auto& [_, v] : mp) res.push_back(std::move(v));
        return res;
    }
};

复杂度

• 时间 O(n · k log k)，n 是单词数，k 是平均长度
• 空间 O(n · k)

易错 / 回顾

• 不能直接对原 string 排序——会改原数据
• 用 std::move 把 vector 移出 map，避免拷贝
• 计数版 key：长度 26 的 int[26] 拼成字符串当 key