2019-11-18 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

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

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

C++1

思路：题目相当于讲一个字符串数组进行分组，包含同样字母的单词分到一个组，每个小组中必须是字母异位词，不能有相同的单次出现。那么可以使用hash映射来做，先遍历一次字符串数组，将单词分别做排序，这样可以找出几种包含不同字母的单词，记下hash表的大小size_，记为最后要返回的二维数组的行数。接下来就可以通过这个hash表来对每个字符串再遍历一次，每次先做重新排序后和hash表中的键进行对比，当匹配的时候，将原单词（排序之前）存进对应行数的数组中，直接使用push_back即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        sort(strs.begin(), strs.end());
        unordered_map<string, int> hm;
        string temp;
        int index=0;
        for(string s:strs){
            temp = s;
            sort(temp.begin(), temp.end());
            if(hm.count(temp)<=0){
                hm.insert(make_pair(temp, index++));
            }
        }
        int size_ = hm.size();
        vector<vector<string> > res(size_);
        for(string ss:strs){
                temp = ss;
                sort(temp.begin(), temp.end());
                if(hm.count(temp)>0){
                    res[hm[temp]].push_back(ss);
                }
            }
        return res;
    }
};