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; }