# 49 - Group Anagrams

解法一 - 用 sort 完的結果來分類

最直觀的想法就是用 sort 完的 string 來分類，這樣同屬一個 anagram group 的就會被分到一起。

我們可以用一個 hash table， key 就是 sort 完的 anagram string，value 就是那個 anagram 的 vector。

實作如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;

        for(int i = 0; i<strs.size(); i++) {
            string s = strs[i];
            sort(s.begin(), s.end());
            m[s].push_back(strs[i]);
        }

        vector<vector<string>> res;
        for (auto &i : m) 
            res.push_back(i.second); 

        return res;
    }
};

假設所有要處理的字串中，最長的長度是 K，那時間複雜度是 O(NKlogK)。

Runtime: 36 ms, faster than 91.78% of C++ online submissions for Group Anagrams. Memory Usage: 19.1 MB, less than 59.66% of C++ online submissions for Group Anagrams.

解法二 - 用各字母出現的次數來分類

因為每次 sort 的時間是 O(KlogK)，如果我們可以不用 sort，那時間複雜度就會下降。比如說我們可以把每個字母出現的次數都數一數，然後 concatenate 起來變成一個字串當作 key。

不過感覺 Leetcode 上的 test case 大多數都是短字串，所以用這種做法反而會讓 key 裡面有很多無用的 0。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        vector<int> count(26);

        for(int i = 0; i<strs.size(); i++) {
            // Build key by counting the appearance of each char
            string key;
            fill(count.begin(), count.end(), 0);
            for(auto &c: strs[i]) count[c-'a']++; 
            for(int p=0; p<count.size(); p++) 
                key += to_string(count[p]);

            m[key].push_back(strs[i]);
        }

        vector<vector<string>> res;
        for (auto &i : m) 
            res.push_back(i.second); 

        return res;
    }
};

Runtime: 104 ms, faster than 13.93% of C++ online submissions for Group Anagrams. Memory Usage: 21 MB, less than 22.42% of C++ online submissions for Group Anagrams.