字母异位词分组

C++ 解法, 执行用时: 22ms, 内存消耗: 6624KB, 提交时间: 2022-02-10

class Solution {
public:
    /*
    方法一：排序
    由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，
    故可以将排序之后的字符串作为哈希表的键。
    
    复杂度分析
    时间复杂度：O(nklogk)，其中 n 是 }strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
               需要遍历 n 个字符串，对于每个字符串，需要 O(klogk) 的时间进行排序以及O(1) 的时间更新哈希表，
               因此总时间复杂度是 O(nklogk)。
    空间复杂度：O(nk)，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度。
               需要用哈希表存储全部字符串。
    */
    vector<vector<string>> groupAnagrams1(vector<string>& strs) {
        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;
    }
    
    /*
    方法二：计数

    1. 由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，
       故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。
    2. 由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。
       需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。
       
    复杂度分析
    时间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的的最大长度，Σ 是字符集，
               在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历 n 个字符串，对于每个字符串，
               需要 O(k) 的时间计算每个字母出现的次数，O(∣Σ∣) 的时间生成哈希表的键，以及 O(1) 的时间更新哈希表，
               因此总时间复杂度是 O(n(k+∣Σ∣))。
    空间复杂度：O(n(k+∣Σ∣))，其中 n 是 strs 中的字符串的数量，k 是 strs 中的字符串的最大长度，Σ 是字符集，
               在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，
               而记录每个字符串中每个字母出现次数的数组需要的空间为 O(∣Σ∣)，
               在渐进意义下小于 O(n(k+∣Σ∣))，可以忽略不计。
    */
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res ;
        map<string, vector<string>> map ;
        
        // 统计string的各字母频次,以频次为key直接加入队列
        for (auto s : strs) {
            string sts = string(26, '0') ;
            for (auto c : s)  ++ sts[c-'a'] ;
            map[sts].emplace_back (s) ;
        }
        for (auto e : map)  res.emplace_back(e.second) ;
        
        return res ;
    }
};

C++ 解法, 执行用时: 27ms, 内存消耗: 6928KB, 提交时间: 2022-03-20

#include<bits/stdc++.h>
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        auto arrayHash = [fn = hash<int>{}] (const array<int, 26>& arr) -> size_t {
            return accumulate(arr.begin(), arr.end(), 0u, [&](size_t acc, int num) {
                return (acc << 1) ^ fn(num);
            });
        };

        unordered_map<array<int, 26>, vector<string>, decltype(arrayHash)> mp(0, arrayHash);
        for (string& str: strs) {
            array<int, 26> counts{};
            int length = str.length();
            for (int i = 0; i < length; ++i) {
                counts[str[i] - 'a'] ++;
            }
            mp[counts].emplace_back(str);
        }
        vector<vector<string>> ans;
        for (auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

C++ 解法, 执行用时: 30ms, 内存消耗: 6588KB, 提交时间: 2022-07-19

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > groupAnagrams(vector<string>& strs) {
        // write code here
        vector<vector<string>> res;
        unordered_map<string,vector<string>> map;
        for(auto& s:strs){
            string str=string(26,0);
            for(auto c:s) str[c-'a']++;
            map[str].emplace_back(s);
        }
        for(auto& e:map) res.push_back(e.second);
        return res;
    }
};

C++ 解法, 执行用时: 31ms, 内存消耗: 6580KB, 提交时间: 2022-02-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string,vector<string>> map;
        for(auto s:strs)
        {
            string sts=string(26,'0');
            for(auto c:s)
                ++sts[c-'a'];
            map[sts].emplace_back(s);
        }
        for(auto e:map)
            res.emplace_back(e.second);
        return res;
    }
};

C++ 解法, 执行用时: 31ms, 内存消耗: 6592KB, 提交时间: 2022-06-13

class Solution {
  public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> v ;
        map<string, vector<string>> map ;
        for (auto s : strs) {
            string k = string(26, '0') ;
            for (auto c : s)  ++ k[c - 'a'] ;
            map[k].emplace_back (s) ;
        }
        for (auto e : map)  v.emplace_back(e.second) ;
        return v ;
    }
};

详情