yicong@algo: ~/code/01-hash/0049-group-anagrams.cpp

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;
}