题目

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

示例

输入：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;
  }
};

小结

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