前言

中秋連假第一天，來開啟一系列的題目練習~ 今天挑戰的是top 100 liked中hash table相關的題目─49. Group Anagrams。
所謂Anagrams就是可以用同樣的一組字元重新排列組合的字串們~ 可以思考一下你會怎麼做呢？

想法

先不論是否為hash table類型的題目，遇到了要歸類的情形，會想到的就是要讓它們可以對到同一個類，而在這種情況下，用map或unordered_map就再適合不過了~ 而map跟unordered_map顧名思義就差在是否會對map裡的key進行排序，可以視情況採用。
那要怎麼怎麼讓同一組anagrams歸到同一類呢？我們可以知道如果是屬於同一組anagrams，字串裡面的字元出現頻率必定一樣，例如abcc跟ccba，都是ax1，bx1，cx2的情形，那直覺的方式就是再做一次字串統計表，讓每個頻率組合變成一個key，例如"a1b1c2"，每次統計字串所花費的時間就是O(n)。
不過，後來我採用的是另外一種做法，雖然時間複雜度略高一些，但寫起來會比較簡單一點，不用另外自己寫一個函式，就是用sort。因為既然組成的元素跟頻率都一樣，那這個字串sort過之後的string應該也會相等，例如abcc、ccba，排序都會變成abcc。
而字串的sort就跟vector的sort差不多：sort(s.begin(),s.end())，不過sort的時間複雜度就是O(nlogn)了。
藉著算出每個string的key，我們就可以用map來把sort後的string當key，而不斷push_back屬於該類的string；最後則再遍歷整個map來存到答案中。程式碼如下：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // key as sorted string
        map<string, vector<string>> ansM;
        vector<vector<string>> ans;
        // group by sorted string
        string sortedS;
        for(int i=0;i<strs.size();++i){
            sortedS = strs[i];
            sort(sortedS.begin(),sortedS.end());
            ansM[sortedS].push_back(strs[i]);
        }
        // push saved map to ans
        for(auto &i:ansM){
            ans.push_back(i.second);
        }
        return ans;
        
    }
};

時間複雜度應是O(nklogk)，n為總共string的數量，而k則為每個string的長度。
至於前面用"a1b1c2"這種字串當key的方式，也可以自行實作看看，理論上可以達到更佳的時間複雜度(O(nlogk))。

結語

假日就有比較充裕的時間練習新題目了，趁有空的時候多累積一些吧XD