題目網址：https://leetcode.cn/problems/group-anagrams/

題意：給一 string list strs, 其中 strs[i] 僅由小寫字母所組成, 將 strs 中的字母異位詞 (Anagram) 進行分組, 可按任意順序返回。

字母異位詞 (Anagram) 定義 ：若 s 和 t 中每個字母的出現次數都相同, 則 s 和 t 互為字母異位詞。

Solution 1：

想法：利用 Sorting + hash table, 遍歷每個 string s, 並對其進行排序得到 string key, 將 key 和對應的 s 加入到 hash table 中。最後再根據 key 取出整個 group 即可

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const auto& s : strs) {
            string key = s;
            sort(key.begin(), key.end());
            groups[key].emplace_back(s);
        }

        vector<vector<string>> res;
        for (const auto& [key, group] : groups) {
            res.emplace_back(group);
        }
        return res;
    }
};
  • time：$O(m \cdot n \cdot log(n))$ ➔ 其中 m 為 string 的個數, n 為 string 的平均長度。
    • $O(n \cdot log(n))$：s 進行 sorting 的時間
  • space：$O(m \cdot n)$ ➔ hash table 中儲存所有的 string

Solution 2：

想法：利用 hash table, 紀錄每個 string s 中每種 char 出現的頻率, 並把每種 char 的頻率當作是 key, 連同 s 一起加入到 hash table 中

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> groups;
        for (const auto& str : strs) {
            string freqs(26, '0'); // 用 string 代替 vector 紀錄出現頻率
            for (const auto& ch : str) {
                freqs[ch - 'a']++;
            }
            groups[freqs].emplace_back(str);
        }

        vector<vector<string>> res;
        for (const auto& [freq, group] : groups) {
            res.emplace_back(group);
        }
        return res;
    }
};
  • time：$O(m \cdot n)$ ➔ 所有 string 中每種 char 的出現頻率, 其中 m 為 strs 的元素個數, n 為 strs[i] 的平均長度
  • space：$O(m \cdot n)$ ➔ groups 儲存所有的 string