runtime 30 ms, beats 98.10% of cpp submissions
O(mn x log(m)) solution with explanation

tags: hashmap, sorting, string

Group Anagrams

📖 description

給定一個字串陣列 strs ，將字串分類並組成群組，組成的邏輯是將 anagrams 的字串組在一起，表示使用的字元都相同，排列順序可相同可不相同。

ex.
    Input: 
        strs = ["eat","tea","tan","ate","nat","bat"]

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

🧠 solution

使用 sort 將每個字串利用 anagrams 分類，因為使用相同字元表示 sort 後的結果是相同的，以此當作 hash table 的 key ，就可以把群組分開。

⏳ time complexity

定義 m 為 字串的長度 ，對每個字串 sort 需要 *O(mlog(m))*，共有 n 個字串，時間複雜度 O(mn x log(m))
總時間複雜度 O(mn x log(m))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string,vector<string>> m;
        string tmp;
        for(int i=0;i<strs.size();i++){
            tmp = strs[i];
            sort(tmp.begin(),tmp.end());
            m[tmp].emplace_back(strs[i]);
        }
        for(auto item : m){
            ans.emplace_back(item.second);
        }
        return ans;
    }
};