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

題目大意

給定字符串數組，返回所有字母異位詞分組（即由相同字母重新排列形成的單詞）。所有輸入小寫字母。

解法思路

字母異位詞排序後相同。用 map 記錄「排序後字符串 → 首次出現下標」。

• 遍歷數組，對每個字符串排序得到 key
• 若 key 不在 map：記錄下標
• 若 key 在 map 且值 ≥ 0：說明是第二次出現，先加入首次出現的字符串，將值標記為 -1
• 當前字符串加入結果

完整代碼

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        unordered_map<string, int> mp;
        for (int i = 0; i < strs.size(); i++) {
            string s = strs[i];
            sort(s.begin(), s.end());
            if (mp.count(s)) {
                if (mp[s] >= 0) {
                    res.push_back(strs[mp[s]]);
                    mp[s] = -1;
                }
                res.push_back(strs[i]);
            } else {
                mp[s] = i;
            }
        }
        return res;
    }
};

複雜度分析

設 n = 字符串數量，m = 平均長度。排序 O(m log m)，總時間 O(n * m log m)，空間 O(n * m)。