49.Group anagrams

Given an array of strings, group anagrams together.

For example, given:["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

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

One slower version is to use sorted stringas the key, and for each string a sort operation is required to compute the key. The complexity isO(n * m log m)

where n is the number of strings, and m is the length of each string.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        map<string, vector<string> > mp;
        for (int i=0;i<strs.size();++i){
            string key = strs[i];
            sort(key.begin(), key.end());
            if (mp.find(key) == mp.end()){
                mp[key] = vector<string>(1,strs[i]);
            }else{
                mp[key].push_back(strs[i]);
            }
        }

        for (auto it = mp.begin(); it !=mp.end(); it++){
            res.push_back(it->second);
        }
        return res;

    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> res;
        int primes[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
        map<int, int> mp;
        int key;
        int count = 0;
        for (int i=0; i<strs.size();++i){
            key = 1;
            for (int j=0; j < strs[i].size();++j){
                key *= primes[strs[i][j]-'a'];
            }
            if (mp.find(key) == mp.end()){
                mp[key] = count++; 
                res.push_back(vector<string>(1, strs[i]));// vector<String>(1,strs[i]) 创建一个大小是1 的vector，里面放一个strs[i]
            }else{
                res[mp[key]].push_back(strs[i]);
            }
        }

        return res;

    }
};

REF:

• [http://yucoding.blogspot.ca/2016/12/leetcode-question-group-anagrams.html]