49. Group Anagrams 群组错位词

Given an array of strings, group anagrams together.

Example:
 
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

All inputs will be in lowercase. The order of your output does not matter.

解法1

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    vector<vector<string>> res;
    unordered_map<string, vector<string>> m;
    for (string str : strs) {
        string t = str;
        sort(t.begin(), t.end());
        // 这里可以不用判断m[t]存不存在
        m[t].push_back(str);
    }
    for (auto a : m) {
        res.push_back(a.second);
    }
    return res;
}

解法2

不对字符串进行排序后当做key. 不过实际效率没解法1高.

vector<vector<string>> groupAnagrams2(vector<string>& strs){
    vector<vector<string>> res{};
    unordered_map<string,vector<string>> m{};
    for (string str : strs){
        vector<int> cnt(26,0);
        string t = "";
        for (char c: str) ++cnt[c-'a'];
        for (int d : cnt) t+=to_string(d)+"/";
        m[t].push_back(str);
    }
    for (auto a : m){
        res.push_back(a.second);
    }
    return res;
}
 
comments powered by Disqus