字母异位词分组

题意

给定字符串数组 strs，把字母异位词分在同一组。可以按任意顺序返回结果。

字母异位词（anagram）指由相同字母重新排列形成的词，例如 "eat"、"tea"、"ate"。

思路

最直接的做法是：对每个字符串排序，排序结果相同的词就是异位词。

排序需要 $O(k \log k)$ 处理一个词，总复杂度 $O(n \cdot k \log k)$ 。对于 $n \le 10^4$ 、 $k \le 100$ 可以接受，但并非最优。

优化的关键是：异位词的字母构成完全一样，因此可以用 26 个字母的计数作为分组 key。构造 key 的时间只需 $O(k)$ ，且 key 长度固定（26 个计数值串接）。

另一种备选方案是用质数乘积做 key——每个字母映射到一个质数，乘积相同的词一定是异位词。但 $k=100$ 时乘积可能溢出 64 位整数，需要大整数或模数，不推荐。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-28 21:58
 * update_at: 2026-07-28 21:58
 */
// brute.cpp：排序字符串作 key，分组输出。
// O(n * k log k)，适合小数据，帮助理解题意。
#include <bits/stdc++.h>
using namespace std;

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

// 本地测试 adapter，提交 LeetCode 时只保留 Solution 类
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
        cin >> strs[i];

    auto ans = Solution().groupAnagrams(strs);
    for (auto &group : ans) {
        for (size_t i = 0; i < group.size(); i++) {
            if (i)
                cout << ' ';
            cout << group[i];
        }
        cout << '\n';
    }
    return 0;
}

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-28 21:58
 * update_at: 2026-07-28 21:58
 */
// main.cpp：26 字母计数 key，每组异位词只需 O(k) 构造 key。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        unordered_map<string, vector<string>> groups;
        for (const string &s : strs) {
            array<int, 26> cnt = {};
            for (char ch : s)
                cnt[ch - 'a']++;
            string key;
            for (int c : cnt)
                key += to_string(c) + "#";
            groups[key].push_back(s);
        }
        vector<vector<string>> ans;
        for (auto &[_, v] : groups)
            ans.push_back(move(v));
        return ans;
    }
};

// 本地测试 adapter，提交 LeetCode 时只保留 Solution 类
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<string> strs(n);
    for (int i = 0; i < n; i++)
        cin >> strs[i];

    auto ans = Solution().groupAnagrams(strs);
    for (auto &group : ans) {
        for (size_t i = 0; i < group.size(); i++) {
            if (i)
                cout << ' ';
            cout << group[i];
        }
        cout << '\n';
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25#!/usr/bin/env python3
from typing import List
from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        groups = defaultdict(list)
        for s in strs:
            key = "".join(sorted(s))
            groups[key].append(s)
        return list(groups.values())


def main() -> None:
    n = int(input())
    strs = input().split()
    assert len(strs) == n
    ans = Solution().groupAnagrams(strs)
    for g in ans:
        print(" ".join(g))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n \cdot k)$ ，每个词需要一次 $O(k)$ 的计数和 key 构造。
空间复杂度： $O(n \cdot k)$ ，哈希表存储所有词的 key 和分组结果。

总结

把"排序比较"转化为"计数比较"是处理异位词的常用手法，核心是定义一个函数 $f(s)$ ，使得 $f(s_1) = f(s_2)$ 当且仅当 $s_1, s_2$ 是异位词。

目录

题意

思路

代码

复杂度

总结