每日算法之三十八：Anagrams 分組——排序+哈希表 O(N·KlogK) 解法

題目描述

給定字符串數組，返回所有由互為字母異位詞（Anagrams）組成的分組。字母異位詞定義：兩字符串字母種類與個數完全相同。注意：單個字符串不構成分組，至少需要兩個。

核心思路：統一特徵值 + 哈希分組

將每個字符串排序後作為特徵值，互為字母異位詞的字符串排序結果相同。使用 map<string, int> 記錄特徵值首次出現的下標。

演算法流程

1. 遍歷字符串數組，對每個字符串排序得到 s。
2. 查找 map 中是否存在 s：
   • 不存在：存入 map[s] = i（記錄首次出現位置）。
   • 存在：
     • 若 map[s] >= 0，說明首次出現的原始字符串尚未加入結果，先加入 strs[map[s]]，並將 map[s] = -1 標記已加入。
     • 加入當前字符串 strs[i] 到結果。

代碼實現（C++）

class Solution {
public:
    vector<string> anagrams(vector<string> &strs) {
        vector<string> res;
        if (strs.size() <= 1) return res;

        map<string, int> anagram; // 特徵值 -> 首次下標（-1 表示已加入結果）

        for (int i = 0; i < strs.size(); i++) {
            string 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 · K log K) —— N 個字符串，平均長度 K，排序耗時 K log K。
• 空間：O(N · K) —— 存儲排序後的特徵值與結果。

優化方向

• 使用 unordered_map 替代 map，查找平均 O(1)。
• 特徵值可用字符頻率統計（26 個小寫字母）代替排序，時間降為 O(N · K)。

示例

輸入：["eat", "tea", "tan", "ate", "nat", "bat"]
排序特徵值："aet", "aet", "ant", "aet", "ant", "abt"
輸出：["eat", "tea", "ate", "tan", "nat"]（"bat" 無異位詞，不輸出）

總結

本題核心在於「排序後的字符串作為特徵值」這一轉化，配合哈希表分組，是處理字母異位詞問題的通用模板。