30-Day LeetCoding Challenge (Day6)

Blue Monday 迎來挑戰開始後的第一題 Medium：49. Group Anagrams
題目給定多個字串，判斷他們是不是同類。只要包含的字元完全相同就算同類，不考慮順序。

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

在開始寫之前需要先修一下 C++ 另外一種強大的 container：map/unordered_map
👉 https://mropengate.blogspot.com/2015/12/cc-map-stl.html
👉 https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/

解題思路是對每個 strs 排序，之後透過 map 找到對應的 vector 並 push 進去，最後再把 map 的 vector 輸出到 ans 中。
結果這樣竟然花了 140ms，完全吊車尾。

static int __ = [](){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;

        if(strs.empty())
            return ans;

        unordered_map<string, vector<string>> m;

        for(int i=0; i<strs.size(); i++){
            string tmp = strs[i];
            sort(tmp.begin(), tmp.end());
            if(m.find(tmp) == m.end())
                m.insert(pair<string, vector<string>> (tmp, {strs[i]}));
            else
                m[tmp].push_back(strs[i]);
        }
        
        unordered_map<string, vector<string>>::iterator it = m.begin(); 
    	while (it != m.end())
	    {
    		ans.push_back(it->second);
        	it++;
	    }

        return ans;
    }
};

馬上來改寫一下，把最後的迴圈拿掉，一開始就用 map 紀錄對應的 ans[idx]，直接把 strs 推到最後輸出的 vector 裡面。
不知道跟 server 忙不忙有沒有關係，時間飄動幅度有點大，不過大概是到 5x ms 左右了。

static int __ = [](){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        int idx = 0;

        if(strs.empty())
            return ans;

        unordered_map<string, int> m;

        for (auto str : strs) {
            string tmp = str;
            sort(tmp.begin(), tmp.end());

            if(m.find(tmp) == m.end()) {
                ans.push_back({str});
                m[tmp] = idx++;
            }
            else
                ans[m[tmp]].push_back(str);
        }

        return ans;
    }
};

總結下這個算法時間複雜度會是 N 個字串 * K(logK) 字串長度，官方解法二找 Key 的方式只要Ｋ，程式碼如下。
另外也有網友整理其它方式，有興趣可以過去參考看看 👉https://leetcode.wang/leetCode-49-Group-Anagrams.html
果然 Medium 開始演算法好壞對時間差異的影響就看得出來了，每一題都乾貨滿滿啊。

static int __ = [](){
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, int> m;
        int cnt = 0;

        for (auto str : strs) {
            int idx[26] = {0};

            for(int i=0; i< str.size(); i++)
                idx[str[i] - 'a']++;

            string key = "";
            for(int i=0; i<26; i++)
                key += '#' + to_string(idx[i]);

           if(m.find(key) == m.end()) {
                ans.push_back({str});
                m[key] = cnt++;
            }
            else
                ans[m[key]].push_back(str);
        }
        
        return ans;
    }
};

題外話在看其他人的程式碼時發現有些人會使用 map::count，好奇查了一下這是什麼用法
下面兩個 spec 都寫就是去找 Key 存不存在，因為在 map 中 Key 是獨一無二的，所以就只有 1/0
👉 std::map::count
👉map count() function in C++ STL

實際翻了一下 source code，註解也明文寫著這個是在 multimaps 才有意義；對 map 而言就是 find 看有找到還是沒找到而已。

+ if (!m.count(tmp))
- if (m.find(tmp) == m.end())

// https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_map.h
1206      //@{
1207      /**
1208       *  @brief  Finds the number of elements with given key.
1209       *  @param  __x  Key of (key, value) pairs to be located.
1210       *  @return  Number of elements with specified key.
1211       *
1212       *  This function only makes sense for multimaps; for map the result will
1213       *  either be 0 (not present) or 1 (present).
1214       */
1215      size_type
1216      count(const key_type& __x) const
1217      { return _M_t.find(__x) == _M_t.end() ? 0 : 1; }

檢視文章