yicong@algo:~/code/01-hash$ cat 0049-group-anagrams.cpp
49. 字母异位词分组
// 思路
每个串排序后作为哈希表的 key;或用字符频次作为 key
// 时间复杂度
O(n·k log k),n 个串、平均长度 k,每个串要排序
// 空间复杂度
O(n·k),需要存下所有字符串
// 易错点
结果分组的顺序不重要,但组内元素必须来自同一组异位词;别忘 return ans
// 面试口述要点
排序做 key 是 O(n·k log k),计数做 key 可优化到 O(n·k);
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> m;
for (string& s : strs) {
string key = s;
sort(key.begin(), key.end());
m[key].push_back(s);
}
vector<vector<string>> ans;
for (auto& [key, group] : m) ans.push_back(move(group));
return ans;
}
};
// 本地测试:输入 n,然后 n 个单词;每行输出一组
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) return 0;
vector<string> strs(n);
for (string& s : strs) cin >> s;
vector<vector<string>> ans = Solution().groupAnagrams(strs);
for (auto& group : ans) {
for (size_t i = 0; i < group.size(); ++i)
cout << group[i] << (i + 1 == group.size() ? '\n' : ' ');
}
return 0;
}