题目描述
给定一组字符串，将所有字母顺序颠倒的字符串归为一组。

注意：

• 所有输入均是小写字母

• 输出顺序随意

样例
输入：

["eat", "tea", "tan", "ate", "nat", "bat"]

输出：

[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

算法
(哈希表+计数排序) $O(NL)$

定义从string 映射到vector<string>的哈希表：unordered_map<string, vector<string>>
将每个字符串的所有字符从小到大排序，将排好序的字符串作为key，然后将原字符串插入key对应的vector<string>中。

时间复杂度分析：$N$是字符串个数，$L$是字符串平均长度。对于每个字符串，哈希表和vector的插入操作复杂度都是 $O(1)$，计数排序的复杂度为$O(L)$。所以总时间复杂度是$O(NL)$。

C++代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> dict;
        string str;
        int count[255];
        for(int i = 0; i < strs.size(); i ++){
            str = strs[i];
            string key = "";
            memset(count, 0, sizeof count);
            for(int j = 0; j < str.length(); j ++){
                count[str[j]] ++; // 统计各个字母出现的次数
            }
            for(int j = 'a'; j <= 'z'; j ++){
                while(count[j] --){
                    key += j; // 按顺序将字母加入key中
                }
            }
            dict[key].push_back(str);
        }
        vector<vector<string>> res;
        unordered_map<string, vector<string>>::iterator it;
        for(it = dict.begin(); it != dict.end(); it ++){
            res.push_back(it->second);
        }
        return res;
    }
};