单词分类

题意

给出 n 个只含大写字母的单词。

如果两个单词中每个字母出现次数完全相同，就把它们归为同一类。

要求输出总共有多少类。

思路

这题的关键是给每个单词找一个统一的“标准形”。

最直接的教学版写法如下：

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// brute.cpp：把每个单词排序成标准形后去重，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

int n;
set<string> classes_of_words;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        // 排序后的结果只和每个字母出现次数有关。
        sort(s.begin(), s.end());
        classes_of_words.insert(s);
    }

    cout << classes_of_words.size() << '\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#include <bits/stdc++.h>
using namespace std;

int n;
set<string> classes_of_words;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        // 同一类单词排序后一定得到同一个标准形。
        sort(s.begin(), s.end());
        classes_of_words.insert(s);
    }

    cout << classes_of_words.size() << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n * L log L)$
空间复杂度： $O(nL)$

其中 L 是单词长度。

总结

这题本质上是在数“有多少种不同的标准形”。

把异位词问题转成排序后去重，是最直接也最稳的写法。

目录

题意

思路

代码

复杂度

总结