题目

给你一个字符串数组，将字母异位词组合在一起。字母异位词是由重新排列源单词的字母得到的新单词，源单词中的每个字母通常恰好使用一次。

示例

输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出：[["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

分组内部的顺序不限，分组的顺序也不限。

思路

先观察一组异位词：eat、tea、ate。它们包含的字母完全相同（e、a、t），只是排列顺序不同。

如果把每个单词的字母按字典序排好，这三个单词会得到同一个结果：aet。也就是说，排序后的字符串可以唯一标识一组异位词。两个单词互为异位词，当且仅当它们排序后的结果相等。

方法一

基于这一点，做法分三步：

  1. 准备一个哈希表：键为排序后的字符串，值为该组单词的列表。
  2. 遍历每个单词：将字母排序得到键，把原单词加入对应的分组。
  3. 遍历完成后，哈希表中的每个值就是一个分组，全部收集起来返回。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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& p : groups) {
            ans.push_back(p.second);
        }
        return ans;
    }
};

复杂度分析

设单词个数为 n，最长单词长度为 k。

  • 时间复杂度：每个单词排序耗时 O(klog k)，整体为 O(nklog k)。
  • 空间复杂度：哈希表存放全部单词，为 O(nk)。

方法二：用字母计数代替排序

当字符集固定（例如只含小写字母）时，可以用每个字母的出现次数作为分组依据，省去排序：

  • 统计单词中 26 个字母各出现几次，把计数结果编码成一个字符串作为键。
  • 每个单词的统计耗时 O(k)，整体为 O(nk)，在单词较长时优于排序法。
  • C++ 中可以用 array<int, 26> 完成统计，再把计数拼成字符串。

判断两个字符串是否互为异位词，有两种等价方式：排序后相等，或者字母计数相同。按数据规模和个人习惯选择即可。

两个词互为异位词，等价于：26 个字母各自出现的次数完全相同。排列顺序不影响计数。
eat拆成字母：e a t,
统计：a 1 次，e 1 次，t 1 次；
tea拆成字母：t e a,
统计：a 1 次，e 1 次，t 1 次。
顺序不同，但统计结果一样，所以它们分到同一组。这就是计数法的依据。

单词 各字母出现次数（非零部分） 计数 key 归属组
eat a1 e1 t1
tea a1 e1 t1
ate a1 e1 t1
tan a1 n1 t1
nat a1 n1 t1
bat a1 b1 t1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
  vector<vector<string>> groupAnagrams(
    vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (string& s : strs) {
      array<int, 26> cnt{}; // 26 个计数
      for (char c : s) cnt[c - 'a']++;
      string key;
      for (int i = 0; i < 26; ++i) {
        key += '#'; // 分隔符
        key += to_string(cnt[i]);
      }
      groups[key].push_back(s);
    }
    vector<vector<string>> ans;
    for (auto& p : groups)
      ans.push_back(p.second);
    return ans;
  }
};

值得注意的是：

为什么计数法一定正确？

两个单词互为异位词，当且仅当 26 个字母的计数向量完全相同。这是充要条件：计数相同说明字母构成相同，只是排列不同；计数不同说明至少某个字母数量不一样，不可能是异位词。排序法只是间接地实现了这个判断，计数法直接用了这个条件。

array<int,26> 为什么能直接统计？

小写字母只有 26 个，c - 'a' 把字符映射到 0~25 的桶下标，O (1) 完成 “这个字母出现次数加一”。字符集固定，是计数法成立的前提；如果字符串可能含任意 Unicode 字符，就没法用固定数组，这时排序法更通用。

两种编码的取舍：图里演示用的是 “a1e1t1” 这种压缩写法（直观），实际提交常用 “#1#0#0…” 定长串（26 位、无歧义）。两者都能当 key，只要保证 “计数相同则 key 相同、计数不同则 key 不同” 即可。

什么时候选它？

单词普遍很长（k 大）时计数法优势明显；单词都很短时，两者差距可以忽略，排序法代码更短、更好写。面试时两个都讲、并说明选择依据，是比较完整的回答。

这类”按特征分组”的问题，通用做法是：先找出一个能代表等价类的特征（这里选取排序结果），再用哈希表把特征相同的元素聚拢。用空间换取时间，