Leetcode-49 Group Anagrams

发表于 | 分类于 | 次

Group Anagrams

Given an array of strings, group anagrams together.

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Example 1

1
2
3
4
5
6
7
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

解题思路

若两个字符串是一类的，则对它们排序后是一样的，或者它们拥有各种字母的数量是一样的。可以将排序后的字符串作为键值，对输入的字符串分类。或者，可以统计各字母数量并以此作为键对字符串分类。

复杂度分析

  • 时间复杂度：$O(nklogk)$，n 为字符串数量，k 为字符串最大长度。与 k 有关部分是对字符串的排序时间。
  • 空间复杂度：$O(nk)$，保存结果需要。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
	vector<vector<string>> groupAnagrams(vector<string>& strs) {
		unordered_map<string, vector<string>> mp;
		for (int i = 0; i < strs.size(); ++i) {
			string s = strs[i];
			sort(s.begin(), s.end());
			if (mp.find(s) != mp.end()) {
				mp[s].push_back(std::move(strs[i]));
			}
			else {
				mp.emplace(std::move(s), vector<string>(1, std::move(strs[i])));
			}
		}

		vector<vector<string>> res;
		for (auto &entry : mp) {
			res.push_back(std::move(entry.second));
		}
		return res;
	}
};