时间轴

2025-11-13

init

题目：

P49 字母异位词分组

https://leetcode.cn/problems/group-anagrams/description/?envType=study-plan-v2&envId=top-interview-150

暴力硬比较 TLE

不仅复杂还超时 😢😢😢

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <vector>
#include <string>
#include <unordered_map>

using std::vector;
using std::string;
using std::unordered_map;

class Solution {
    public:
	bool isAnagram(string s, string t)
	{
		if (s.size() != t.size()) {
			return false;
		}
		unordered_map<char, int> smap;
		for (char &ch : s) {
			smap[ch]++;
		}
		for (char &ch : t) {
			if (!smap.count(ch)) {
				return false;
			} else {
				smap[ch]--;
				if (smap[ch] < 0) {
					return false;
				}
			}
		}
		return true;
	}
	vector<vector<string> > groupAnagrams(vector<string> &strs)
	{
		vector<vector<string> > res;
		if (strs.empty()) {
			res.push_back(vector<string>());
			return res;
		}
		if (strs.size() == 1) {
			res.push_back(vector<string>(1, strs[0]));
			return res;
		}
		// 先按size分
		vector<vector<string> > diff_size_strs;
		unordered_map<int, int> size2index;

		for (string &s : strs) {
			if (!size2index.count(s.size())) {
				vector<string> vec;
				vec.push_back(s);
				diff_size_strs.push_back(vec);
				size2index[s.size()] = diff_size_strs.size() - 1;
			} else {
				diff_size_strs[size2index[s.size()]].push_back(s);
			}
		}

		for (vector<string> &vec : diff_size_strs) {
			int n = vec.size();
			int i, j = n - 1;

			while (j >= 0) {
				vector<string> curr;
				string base = vec[j];
				curr.push_back(vec[j]);
				j--;
				for (i = 0; i <= j; i++) {
					if (isAnagram(base, vec[i])) {
						curr.push_back(vec[i]);
						swap(vec[i], vec[j]);
						j--;
						i--; //重新检查当前位置
					}
				}
				res.push_back(curr);
			}
		}
		return res;
	}
};

排序+哈希表

每个字符串的排序后的字符串作为哈希表的 key，哈希表的 value 就是有相同 key 的原字符串。

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
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>

using std::unordered_map;
using std::string;
using std::vector;

class Solution {
    public:
	vector<vector<string> > groupAnagrams(vector<string> &strs)
	{
		vector<vector<string> > res;
		if (strs.empty()) {
			res.push_back(vector<string>());
			return res;
		}
		unordered_map<string, vector<string> > umap;
		for (string &s : strs) {
			string original(s);
			std::sort(s.begin(), s.end());
			if (!umap.count(s)) {
				umap[s] = vector<string>(1, original);
			} else {
				umap[s].push_back(original);
			}
		}
		for (auto [_, vec] : umap) {
			res.push_back(vec);
		}
		return res;
	}
};