LeetCode 筆記：Anagrams（字母異位詞分組）

題目描述

給定字串陣列，返回所有屬於同一組字母異位詞的字串。字母異位詞：字母種類與數量相同，順序不同（如 "tea"、"eat"、"ate"）。輸入皆為小寫。

解題分析

核心觀察：將字串按字母排序後，同組異位詞排序結果相同。以排序後字串為 Key，建立 Hash 表（或 Map），值為原字串索引或列表。遍歷陣列，排序每字串查表分組。

C++ 實現

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        string s;
        map<string, int> anagram; // key: 排序後字串, value: 首次出現索引，-1 表示已加入結果
        vector<string> res;
        for (int i = 0; i < strs.size(); ++i) {
            s = strs[i];
            sort(s.begin(), s.end());
            if (anagram.find(s) == anagram.end()) {
                anagram[s] = i;
            } else {
                if (anagram[s] >= 0) {
                    res.push_back(strs[anagram[s]]);
                    anagram[s] = -1;
                }
                res.push_back(strs[i]);
            }
        }
        return res;
    }
};

複雜度與總結

• 時間複雜度：O(N * L log L)，N 為字串數，L 為平均長度（排序耗時）。
• 空間複雜度：O(N * L)。
• 關鍵在於理解異位詞定義，善用排序標準化 + Hash 分組。