550eba79e4d6445a801eec931869ca85.png

【题目】：49. 字母异位词分组

方法1：直接对字符串进行排序后使用map存储相同的字母异位词，再把map的value依次存放到结果中。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> mp;
        for(string str : strs) {
            string temp = str;
            sort(str.begin(), str.end());
            mp[str].push_back(temp);
        }   
        for(auto [key, value] : mp) {
            res.push_back(value);
        }
        return res;
    }
};
  • 时间复杂度: O(nklogk)
  • 空间复杂度: O(n)

字母异位词对应的排序后的字符串是一样的，所以把每个字符串排序后插入以排序后字符串作为key，以原字符串作为value的map中。这个方法虽然简洁，但是取决于每个字符串的长度，排序的时间复杂度是k * logk

方法2：自定义哈希函数

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        unordered_map<string, vector<string>> mp;
        for(string str : strs) {
            vector<int> count(26, 0);
            for(char c : str) {
                count[c - 'a']++;
            }
            string key = "";
            for(int i = 0; i < 26; ++i) {
                key += count[i] + i + 'a';// 使用：每个字符出现的次数 + 字符 作为key
            }
            mp[key].push_back(str);
        }   
        for(auto [key, value] : mp) {
            res.push_back(value);
        }
        return res;
    }
};
  • 时间复杂度: O(n*max(k, 26))
  • 空间复杂度: O(n)

使用每个字符出现的次数 + 字符 作为key。