LeetCode Anagrams 完整解析

給定字串陣列，回傳所有字母異位詞分組（字母組成完全相同的字串）。所有輸入為小寫字母。

核心思路：排序後作為鍵值

字母異位詞排序後結果相同。用 Hash Map 記錄「排序後字串 → 首次出現索引」，第二次出現時將首次與當前字串加入答案。

完整 AC 程式碼

class Solution {
public:
    vector anagrams(vector& strs) {
        vector ans;
        unordered_map mp; // key: sorted string, value: first index (-1 means already added)
        
        for (int i = 0; i < strs.size(); i++) {
            string key = strs[i];
            sort(key.begin(), key.end());
            
            auto it = mp.find(key);
            if (it == mp.end()) {
                mp[key] = i; // 首次出現，記錄索引
            } else {
                if (it->second != -1) {
                    // 第二次出現，首次字串加入答案
                    ans.push_back(strs[it->second]);
                    it->second = -1; // 標記首次已加入
                }
                // 當前字串加入答案
                ans.push_back(strs[i]);
            }
        }
        return ans;
    }
};

關鍵細節

• value = -1 標記：避免第三次出現時重複加入首次字串
• 時間複雜度：O(N × K log K)，N 字串數，K 平均長度
• 空間複雜度：O(N × K)

替代方案：字母頻率作鍵

string getKey(const string& s) {
    int cnt[26] = {0};
    for (char c : s) cnt[c - 'a']++;
    string key;
    for (int i = 0; i < 26; i++) key += '#' + to_string(cnt[i]);
    return key;
}
// 避免排序 O(K log K) → O(K)，適合長字串