字母异位词分组 图解题解

这道题到底在问什么

strs

["eat","tea","tan","ate","nat","bat"]

输出

[[eat,tea,ate],[tan,nat],[bat]]

先想最直接的笨办法

暴力做法是每来一个词，都和已有组逐个比较。比较前还要排序，组一多就慢。（动画第 3 步）

最优解：一步一步想明白

1. 3暴力做法是每来一个词，都和已有组逐个比较。比较前还要排序，组一多就慢。
2. 4把每个词排序后当 key。key 一样，直接塞进同一个桶，哈希表自动帮我们聚合。
3. 5e / a / t异位词不是直接比较原串，而是先把字符拆开，准备归一化。
4. 6key=aet排序后得到 key=aet。这个 key 才是进桶的身份证。
5. 7new bucket哈希表里还没有 aet，就新建一个桶，把 eat 放进去。
6. 8key=aettea 的字母顺序不同，但排序后仍然是 aet，所以它应该回到同一个桶。
7. 9hit aetkey 命中已有桶，tea 不和 eat 逐字符比较，直接加入 aet 组。
8. 10key=anttan 排序后是 ant，和 aet 不一样。新 key，得开新桶。
9. 11new bucket ant哈希表里没有 ant，新建第二个桶，把 tan 放进去。
10. 12key=aetate 字母顺序又不同，排序后还是 aet，应该回到第一个桶。
11. 13same key same bucketate 排序后还是 aet，命中第一个桶。每个词都先排序再归桶，没有凭空分组。
12. 16key 设计对了，分组逻辑就只剩下塞桶。
13. 19wrong key如果直接用原字符串，eat 和 tea 会落到两个桶，分组立刻错。
14. 26这题学完不要乱跳，下一步去 对应专题 连刷同类题；卡住时用 AI 答疑追问“为什么这一步成立”，比只背答案更稳。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs):
        groups = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            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 (string s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto& [key, bucket] : groups) ans.push_back(bucket);
        return ans;
    }
};

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

# 哈希分组三件套：归一化 key → 取桶 → 塞元素
groups = defaultdict(list)
for x in 输入:
    key = 归一化(x)          # 排序串 / 26位计数元组 / 数值本身
    groups[key].append(x)    # 桶不存在 defaultdict 自动建
return list(groups.values())

unordered_map<Key, vector<Item>> groups;
for (auto& x : input) {
    Key key = normalize(x);    // 排序串 / 计数签名
    groups[key].push_back(x);  // [] 自动建空桶
}
// 收集 groups 的所有 value 即答案

Map<Key, List<Item>> groups = new HashMap<>();
for (Item x : input) {
    Key key = normalize(x);    // 排序串 / 计数签名
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(x);
}
// new ArrayList<>(groups.values()) 即答案

复杂度

面试官可能追问