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.

解题思路：

善用STL啊朋友们！！！

我们可以建立一个映射来存储一个字符串到字符串向量的映射关系。

这个key可以由对string进行排序得到。

代码：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ret;
        map<string, vector<string>> m;
        for(string s: strs){
            string temp = s;
            sort(temp.begin(), temp.end());
            m[temp].push_back(s);
        }
        for(auto anagm : m){
            ret.push_back(anagm.second);
        }
        return ret;
    }
};

为了降低时间复杂度，可以对每个字符串进行O(N)处理得到唯一字符串

见：http://www.cnblogs.com/grandyang/p/4385822.html

STL中的sort函数的时间复杂度为Nlog₂N