# 0049. Group Anagrams
###### tags: `Leetcode` `Medium` `HashMap`
Link: https://leetcode.com/problems/group-anagrams/
## 思路
### 方法一
将每个字符串排序，得到相同结果的放在一起，然后就可以return了
### 方法二
给字符串用其出现的字母及出现的次数编码，然后再用map把相同的放在一起
## Code
### 方法一
**注意：sort可以直接用来排序字串**
Time Complexity: **O(NKlog K)**, where N is the length of strs, and K is the maximum length of a string in strs. The outer loop has complexity O(N) as we iterate through each string. Then, we sort each string in O(Klog K) time.

Space Complexity: **O(NK)**, the total information content stored in ans.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string, vector<string>> ans;
        map<string, vector<string>>::iterator it;
        for(int i = 0;i < strs.size();i++){
            string temp = strs[i];
            sort(temp.begin(), temp.end());
            it = ans.find(temp);
            if(it!=ans.end()){
                it->second.push_back(strs[i]);
            }
            else{
                vector<string> temp_vec;
                temp_vec.push_back(strs[i]);
                ans.insert(make_pair<string, vector<string>>((string)temp, (vector<string>)temp_vec));
            }
        }
        vector<vector<string>> result;
        for(it = ans.begin(); it != ans.end(); it++){
            result.push_back(it->second);
        }
        return result;
    }
};

### 方法二
Time Complexity: **O(NK)**, where N is the length of strs, and K is the maximum length of a string in strs. Counting each string is linear in the size of the string, and we count every string.

Space Complexity: **O(NK)**, the total information content stored in ans.

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> ans;
        unordered_map<string, vector<string>>::iterator it;
        vector<vector<string>> result;
        if(strs.size()==0){
            return result;
        }
        for(int i = 0;i < strs.size();i++){
            int dictionary[26] = {0};
            for(int j = 0;j < strs[i].length();j++){
                dictionary[(int)(strs[i][j]-'a')]++;
            }
            string temp;
            for(int j = 0;j < 26;j++){
                temp += "#"+to_string(dictionary[j]);
            }
            it = ans.find(temp);
            if(it == ans.end()){
                vector<string> temp_vector = {};
                ans.insert(make_pair<string, vector<string>>((string)temp, (vector<string>) temp_vector));
            }
            ans.find(temp)->second.push_back(strs[i]);
        }
        
        for(it = ans.begin(); it != ans.end(); it++){
            result.push_back(it->second);
        }
        return result;
    }
};

## Result
实在是没想明白为啥2比1慢
### 方法一
Runtime: 56 ms, faster than **19.59%** of C++ online submissions for Group Anagrams.
Memory Usage: 20.7 MB, less than **41.13%** of C++ online submissions for Group Anagrams.
### 方法二
Runtime: 112 ms, faster than **12.16%** of C++ online submissions for Group Anagrams.
Memory Usage: 24.5 MB, less than **17.10%** of C++ online submissions for Group Anagrams.