leetcode--49--字母异位词分组

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

示例:

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

题目链接：https://leetcode-cn.com/problems/group-anagrams

思路：
1、构建一个字典dict，遍历字符串数组，将字符串进行排序后作为dict的key，字典的value是一个列表，字符串原串作为列表中的元素，通过这种方式即可将字符串字母异位词按照相同的key进行聚集

Python代码：

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """

        dt = {}
        for s in strs:
            s = s.encode('utf-8')
            str_sort  = ''.join(sorted(list(s)))
            if str_sort not in dt:
                dt[str_sort] = [s]
            else:
                dt[str_sort].append(s)

        return dt.values()

C++代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> dt;
        for (string str : strs){
            string str_cp(str);
            sort(str_cp.begin(), str_cp.end());
            if (dt.find(str_cp)==dt.end()){
                vector<string> vec;
                vec.push_back(str);
                dt[str_cp] = vec;
            }else{
                dt[str_cp].push_back(str);
            }
        }
        vector<vector<string>> ret;

        for(auto iter=dt.begin(); iter!=dt.end(); iter++){
            vector<string> value = iter->second;
            ret.push_back(value);
        }
        return ret;
    }
};