這題的目標是將一組字串按照字母異位詞進行分類。字母異位詞指的是兩個或多個字串的字母出現頻次一樣，只是排列順序不同，例如 "eat" 和 "tea"。這類題目考的是如何有效地處理字串和利用資料結構進行分組。

題目：

給定一個字串陣列 strs，需要將其分組，讓相同字母異位詞的字串出現在同一個子集合中。可以按任意順序回傳分組結果。

範例：

輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]

解題思路

將每個字串排序，因為異位詞在排序後會變成相同的字串。例："eat" 和 "tea" 排序後均為 "aet"。

使用 unordered_map 來儲存已排序的字串作為 key，並將相同異位詞的原始字串存放在同一組。

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

        vector<vector<string>> res;
        for (auto& m : map) {
            res.push_back(m.second);
        }
        return res;
    }
};

接著叠代 map 從 m.second 取出的 vector<string> 直接 push_back 進 res 就可以回傳結果了。

另一個方式是用陣列來紀錄26個字母的出現次數，並循序串連26字母的出現次數當作 key，這樣就不需要對 str 排序了，

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        for (auto& str : strs) {
            vector<int> count(26, 0);
            for (char c : str) {
                count[c - 'a']++;
            }
            
            string key;
            for (int c : count) {
                key += '#' + to_string(c);
            }
            map[key].push_back(str);
        }

        vector<vector<string>> res;
        for (auto& m : map) {
            res.push_back(m.second);
        }
        return res;
    }
};

用 # 或其他特殊符號是為了避免 2 和 11 直接拼接而區分不出來的問題，產生出 key 格式會像 "1#0#0#...#1#1#..." 這樣，確保每個字母的計數是分隔開的。

參考：
#49. Group Anagrams