LeetCode Anagrams：哈希表分組字母異位詞

LeetCode Anagrams：哈希表分組字母異位詞

給定字符串數組，返回所有字母異位詞組（至少兩個單詞）。異位詞：字母組成相同，順序不同。

核心思想

對每個單詞字母排序作為 key，相同 key 的單詞歸為一組。

方案一：自定義插入排序構建 key

class Solution {
public:
    vector anagrams(vector& strs) {
        vector res;
        unordered_map> dict;
        for (auto& w : strs) dict[getKey(w)].push_back(w);
        for (auto& g : dict)
            if (g.second.size() > 1)
                res.insert(res.end(), g.second.begin(), g.second.end());
        return res;
    }
private:
    string getKey(string w) {
        string key;
        for (char c : w) {
            int i = 0;
            while (i < key.size() && key[i] <= c) i++;
            key.insert(key.begin() + i, c);
        }
        return key;
    }
};

方案二：STL sort 構建 key（更簡潔高效）

class Solution {
public:
    vector anagrams(vector& strs) {
        vector res;
        unordered_map> dict;
        for (auto& w : strs) {
            string key = w;
            sort(key.begin(), key.end());
            dict[key].push_back(w);
        }
        for (auto& g : dict)
            if (g.second.size() > 1)
                res.insert(res.end(), g.second.begin(), g.second.end());
        return res;
    }
};

關鍵點

• unordered_map 平均 O(1) 查找/插入。
• 排序 key 長度 ≤ 100（假設），sort 極快。
• 只輸出組大小 > 1 的單詞。
• 輸出順序不限制。

複雜度

• 時間：O(N * K log K)，N 單詞數，K 平均長度。
• 空間：O(N * K)。

優化變體

• 用 26 字母計數數組作 key（如 "#1#0#2..."），避免排序，O(K) 構建 key。
• 原地修改數組輸出，節省空間。

此題是哈希表分組統計的標準應用，「排序字母作標準化 key」是處理異位詞、字母頻率問題的通用技巧。