题目

题解

1. unordered_map排序法

  • 时间复杂度：排序的话算作$O(Klog{K})$,最外层的 for 循环，所以就是 $O(nKlog{K})$。
  • 空间复杂度：$O(NK)$，用来存储结果。

用一个unordered_map存排序后的字符串和该字符串所在res的位置，然后挨个将字符串存入相应的位置。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, int> m;//key值是字符串排序后的值，value是该字母异位词在res中的位置
        for(const auto& str : strs){
            auto t = str;//t用来存排序的str
            sort(t.begin(), t.end());//将t排序
            if(!m.count(t)){//若m中没有这个t
                m[t] = res.size();// 在m中赋值新增一维的位置，即res现有长度(因为res从0开始)
                res.emplace_back();//则在res中增加一维，用来存这个新t的字母异位词,注意要先给m赋值新位置，否则res.size()会多一位
            }
            res[m[t]].push_back(str);//然后将该字符串存入res中

        }
        return res;
    }
};

2. unordered_map计数法

  • 时间复杂度：$O(NK)$
  • 空间复杂度：$O(NK)$，用来存储结果。
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string,int> m;//key值是字符串计数后的字符串，value是该字母异位词在res中的位置
        for(auto& str:strs){
            vector<int> cha(26);//用cha给26个字母计数
            string key_cha;//存最终的转为字符串的计数结果
            for(auto& s:str){
                cha[s-'a']++;
            }//每个字符挨个统计数目
            for(auto& c:cha){
                key_cha += to_string(c);
            }//cha转为字符串
            if(!m.count(key_cha)){
                m[key_cha] = res.size();
                res.emplace_back();
            }//这一块和排序法一样
            res[m[key_cha]].push_back(str);
        }
        return res;
    }
};