力扣.字母异位词分组

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

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

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

示例 2:

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

示例 3:

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

思路

        首先遇到异位词，一定要想到用hash表来解决，首先字符串是无序的，我们可以通过STL中的sort方法将字符串排序，这样所有的异位词都会变成同一种排列顺序的串，于是遍历这个字符串数组，将对应的串当作hash表的键值key，将排序以前的串当作key对应的value,因为返回的仍然是一条条串组成的数组，所以map对应的value类型不能是普通的string，而是一个vector<string>, vector容器中的元素是各种字符串。

（意思就是：建立一个unordered_map<string ,vector<string> >一个字符串 ，str排序后当作key，排序前当value中的一个个子集）。

     遍历strs，遇到相同key的串就添加进容器。

代码如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
       // 用于接收最后的结果
       vector<vector<string>> ret;    
       // 建立一个hash_map
       unordered_map<string,vector<string>> m;

       for (auto& str : strs){
           // 这里一定需要一个中间变量，如果直接用m[str].push_back(str)，
           // str会在排序后错乱，最终插入的str顺序不再是之前的顺序而是排过序后的
           string key = str;

           // 将字符串进行排序，这样异位词排序后，都是一样的key
           sort(key.begin(),key.end());

           // 用相同的key当作键值，并将其对应的原字符串当作value，压入value的vector容器
           m[key].push_back(str);
       }
   
       // 最终遍历m,将相同key对应的value(一个vector<string>容器：存着各种异位词串),分别压入ret    
       // 容器中
       for (auto e : m)
           ret.push_back(e.second);
       
       return ret;
    }
};