LeetCode 49 Group Anagrams

Tag: LeetCode Posted on 2021-05-27 19:22:05 Edited on 2021-05-27 19:24:35 Views: 37

问题分析

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

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

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

我这里想到的一种是构建一个包含 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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/