字母异位词分组 图解题解

这道题真正在问什么

题目给一组单词，要求把「字母完全相同、只是排列顺序不同」的单词归到同一组，返回全部分组，例如 eat、tea、ate 是一组。它本质不是在问「两个词是不是异位词」，而是在问「怎么给 n 个单词按异位关系划分等价类」——想清楚这一点，就能看出两两比较的思路从一开始就走偏了。

为什么不能两两比较判断异位词

最直觉的做法是拿每对单词比一比，统计两边字母出现次数是否一致。判断一对是 O(k)（k 为单词长度），但 n 个单词约有 n²/2 对，整体 O(n²·k)；而且比完还得靠并查集之类的结构才能落成分组，又慢又绕。

换个角度想：分组问题的通用套路是给每个元素算一个「指纹」——同组指纹必然相同、不同组必然不同，然后按指纹归堆。只要指纹算得快，分组就退化成一次哈希表遍历。于是问题变成：什么指纹能唯一刻画「互为异位词」这层等价关系？

为什么排序后的字符串能当 key

两个单词互为异位词，等价于「每个字母出现的次数完全相同」。把字母排序恰好抹掉顺序差异、只保留字母及其个数：eat、tea、ate 排序后都是 aet；反过来，排序结果相同也必然意味着每种字母个数相同。所以「排序后的字母序列」与「互为异位词」是充要条件，拿它当哈希表的 key 既不会错分也不会漏分。注意不能偷懒成「字母集合」——aab 和 ab 的字母集合相同，但出现次数不同，并不是异位词。

哈希表怎么一次遍历完成分组

建一张表，key 是排序后的字母序列，value 是这一组单词的列表。从左到右扫一遍：每个单词先排序算出 key，表里没有这个 key 就新建一组放进去，有就追加到已有的组。这里的关键动作是「追加」而不是「赋值」——Python 写成 groups.setdefault(key, []).append(w)，如果直接对 key 赋新列表，会把同组先来的单词整组覆盖丢掉。扫完把表里所有的组收集起来就是答案。

复杂度怎么算，还能更快吗

时间 O(n·k·log k)：n 个单词各排序一次，每次 O(k·log k)，哈希插入均摊 O(1)。空间 O(n·k)：哈希表要存下全部单词。

想去掉排序的 log，可以换一种指纹：统计 26 个字母各出现几次，拼成形如 a2b1 的计数串当 key，构造一个 key 只要 O(k)，整体降到 O(n·k)。两种 key 都正确：排序版更好写，计数版在单词较长时更快，面试里说清这层取舍就是加分项。

Python

def groupAnagrams(strs):
    groups = {}              # key -> 单词组
    for w in strs:
        key = "".join(sorted(w))  # 排序后的字母序列
        groups.setdefault(key, []).append(w)
    return list(groups.values())

C++

vector<vector<string>> groupAnagrams(vector<string>& strs){
    unordered_map<string, vector<string>> groups;
    for(auto& w : strs){
        string key = w;
        sort(key.begin(), key.end());  // 排序得 key
        groups[key].push_back(w);
    }
    vector<vector<string>> res;
    for(auto& p : groups) res.push_back(p.second);
    return res;
}

Java

List<List<String>> groupAnagrams(String[] strs){
    Map<String, List<String>> groups = new HashMap<>();
    for (String w : strs) {
        char[] cs = w.toCharArray();
        java.util.Arrays.sort(cs);
        String key = new String(cs);   // 排序得 key
        groups.computeIfAbsent(key, x -> new ArrayList<>()).add(w);
    }
    return new ArrayList<>(groups.values());
}