哈希#中等#字母异位词分组

前文

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

正文

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {

    }
};

• vector，map的用法

解法1

先将每个单词字母排序，然后逐个匹配

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string, int> myMap;

        for(auto e: strs) {
            sort(e.begin(), e.end());
            if (myMap[e]) {
                ++myMap[e];
            } else {
                myMap[e] = 1;
            }
        }
        
        for (auto it = myMap.begin(); it != myMap.end(); ++it) {
            vector<string> tmp;
            for(auto e: strs) {
                auto e2 = e;
                sort(e.begin(), e.end());
                if (e == it->first)
                    tmp.push_back(e2);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

会超时，主要在第二个循环时间效率低，每一个都需要匹配一遍。

解法2

主要是优化解法1代码，解法1中第一个循环不需要用数量做值，直接将map的第二个参数改为vector<string>数组即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string, vector<string>> myMap;

        for(auto e: strs) {
            auto e2 = e;
            sort(e.begin(), e.end());
            myMap[e].push_back(e2);
        }
        
        for (auto it = myMap.begin(); it != myMap.end(); ++it) 
            res.push_back(it->second);

        return res;
    }
};

不会超时，并且时间效率和空间效率提交后均能超过一半用户。