ARST打卡第115周[115/521]

 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) {
        // 可以对每个单词进行sort，然后对比是否有，无则计入list，用python写比较方便
        // 不行，这样就nlog(n)*n了...
        // 维护hash表，也要n*n，看看答案吧
        // 2021年07月18日13:44:48 发现自己方法对了，计算时间复杂度计算错了
        // 实际上是n * klog(k) ，hash表是 n * (k + 26)
        // 见https://leetcode-cn.com/problems/group-anagrams-lcci/solution/bian-wei-ci-zu-by-leetcode-solution-g2a8/
        unordered_map<string, vector<string>> mp;
        for (string& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};