LeetCode 49 Group Anagrams

    
        标签：
        
            LeetCode
        
    发布于：2021-05-27 19:22:05
    编辑于：2021-05-27 19:24:35
    浏览量：971

问题分析

暴力解法显然就是首先对列表中的每个字符串排序，然后据此构造前缀树，每个叶节点分别代表一种簇。

但排序开销大且没有必要，问题的关键是如何快速确定两个字符串是否属于同一簇。

我们可以通过设计一种映射算法，只要将满足条件的映射到相同的值就好。

我这里想到的一种是构建一个包含 26 个数值的数组，其初始化为全 0，对字符串中字符的个数计数。

然后使用这个数组作为 key，结合哈希表即可以 O(n) 的时间复杂度解决问题。

注意到 0 <= strs[i].length <= 100，因此我们可以直接用字符串作为数组使用。

32 ms 解法

这个即我的解法，思路和上面所述的一致。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for(auto s : strs) {
            string key(26, char(0));
            for(int i=0;i<s.size();i++){
                key[s[i]-'a']++;
            }
            m[key].push_back(s);
        }
        vector<vector<string>> res;
        for(auto it = m.begin(); it!=m.end();++it){
            if(!it->second.empty()){
                res.push_back(it->second);
            }
        }
        return res;
    }
};

这道题好顺啊，一遍过，开心！

8ms 解法

我淦，MD 这个就直接排序，然后作为 key 存入哈希表，我佛了，这还比我快，摔！

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int n = strs.size();
        vector<vector<string>> sol;
        unordered_map<string, int> mp;
        for(int i = 0; i < n; i++) {
            string temp = strs[i];
            sort(temp.begin(), temp.end());
            if(mp.count(temp)==0) {
                mp[temp]=sol.size();
                sol.push_back({strs[i]});
            }
            else {
                int ind = mp[temp];
                sol[ind].push_back(strs[i]);
            }
        }
        return sol;
    }
};

Links: leetcode-49-group-anagrams