主題: 學習筆記

LeetCode 49：TypeScript Group Anagrams，從排序 key 到計數簽名

整理 Group Anagrams 的排序分組解法，找出重複複製陣列的成本，並比較固定字元集的計數簽名。

這次先用排序後的字串當群組 key。想法很直覺，互為 anagram 的字串排序後一定相同。不過實作時，更新群組的方式會影響實際複雜度。

題目

對應原題：LeetCode 49：Group Anagrams

給定只含小寫英文字母的字串陣列，將互為 anagram 的字串分到同一組。群組順序與同一群組內的字串順序不要求固定。

暴力解會重複比較群組

可以逐一讀取字串，掃描既有群組，並拿每個群組的第一個字串判斷是否為 anagram。若每次比較都靠排序，單次比較是 O(k log k)，其中 k 是字串最大長度。最壞情況下每個字串都屬於不同群組，總時間會是 O(n² × k log k)。

問題在於同一個字串可能被排序和比較很多次。建立一個能代表整個字串的 key，只要算一次就能直接找到群組。

我最先寫的排序 key 解法

function groupAnagrams(strs: string[]): string[][] {
  if (strs.length === 1) return [strs];

  const map = new Map<string, number[]>();

  for (let index = 0; index < strs.length; index += 1) {
    const sorted = strs[index].split("").sort().join("");

    if (map.has(sorted)) {
      map.set(sorted, [...map.get(sorted)!, index]);
    } else {
      map.set(sorted, [index]);
    }
  }

  const result: string[][] = [];

  map.forEach((indexes) => {
    result.push(indexes.map((index) => strs[index]));
  });

  return result;
}

這是我最先寫的解法。每個字串會轉成字元陣列、排序、再組回字串。"eat"、"tea" 和 "ate" 都會得到 "aet"，所以可以用它當 Map key。value 儲存原始陣列索引，最後再轉回原本字串。

功能正確，但 strs.length === 1 的提前回傳不需要。通用迴圈本來就會回傳 [["a"]] 或 [[""]]。

原始寫法的成本

這行每次遇到相同 key 都會建立新陣列：

map.set(sorted, [...map.get(sorted)!, index]);

如果某一群組有 m 個字串，會依序複製長度 1、2 到 m - 1 的索引陣列。這一群就會多做 O(m²) 次索引複製。所有字串都屬於同一群時，這個成本會變成 O(n²)，因此原始實作的最壞時間不是只有排序的 O(n × k log k)，而是 O(n × k log k + n²)。

這不會讓答案錯誤，但面試中值得主動提到。資料量小時不明顯，群組很大時才會出現差異。

從原解法縮短的版本

索引與最後的第二次轉換都不需要。直接把原始字串放進群組，取出既有陣列後用 push() 修改它。

function groupAnagramsBySorting(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();

  for (const str of strs) {
    const key = [...str].sort().join("");
    const group = groups.get(key);

    if (group) {
      group.push(str);
    } else {
      groups.set(key, [str]);
    }
  }

  return [...groups.values()];
}

push() 直接改變 group 指向的陣列，不會重新設定 Map 的 value。以 n 為字串數量、k 為字串最大長度，排序每個字串的時間是 O(n × k log k)。面試通常把 Map 存取視為預期 O(1)。額外空間包含排序後的 key 與群組，最壞是 O(n × k)。

JavaScript 規格不保證 Array.prototype.sort() 使用固定的排序演算法或複雜度，因此這裡的 O(k log k) 是演算法面試的比較排序模型。MDN 的 sort 文件也說明實際複雜度取決於實作。

為什麼 push() 會變成數字

下面兩段程式的效果不同：

const indexes = map.get(key)!;
indexes.push(index);

map.set(key, map.get(key)!.push(index));

第一段保留 Map 裡的陣列，push() 只改變它的內容。第二段把 push() 的回傳值寫回 Map。push() 的回傳值是新陣列長度，例如 2，不是陣列，因此 value 才會被覆蓋成數字。MDN 對 push() 的說明明確指出它會修改陣列並回傳新長度。

Map<string, string[]> 也能讓 TypeScript 在嘗試存入數字時報錯。原本的 new Map() 沒有型別參數，會失去這層保護。

利用題目限制的計數簽名

原題限定小寫英文字母，所以可以用 26 個計數值組成 key。字母出現次數相同時，這個 key 相同，不必排序每個字串。

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  const firstLowercaseCode = "a".charCodeAt(0);

  for (const str of strs) {
    const counts = new Array<number>(26).fill(0);

    for (const char of str) {
      counts[char.charCodeAt(0) - firstLowercaseCode] += 1;
    }

    const key = counts.join("#");
    const group = groups.get(key);

    if (group) {
      group.push(str);
    } else {
      groups.set(key, [str]);
    }
  }

  return [...groups.values()];
}

每個 key 保留 a 到 z 的出現次數。建立 key 的成本是掃描字串，再處理固定 26 個值，所以時間是 O(Σ(|str| + 26))。因為 26 是固定常數，面試中通常寫成 O(n × k)。這個版本只適用於題目的小寫英文字母限制。若字元範圍改成 Unicode，排序 key 或 Map 次數統計比較通用。

正確性與迴圈不變量

排序版本的迴圈不變量是：處理完 strs[0..i] 後，groups 中每個 key 對應的陣列，恰好包含此前綴中排序結果等於該 key 的所有字串。

初始時沒有處理任何字串，不變量成立。每次處理一個字串，都會算出它唯一的排序 key，然後加入對應群組或建立新群組，因此不變量仍成立。迴圈結束後，每個輸入字串都在且只在一個群組中；兩個字串在同一群組，等價於它們排序結果相同，也就是互為 anagram。

計數簽名版本的推理相同，只是 canonical key 從排序後字串改成 26 個字母次數。

最小驗證

LeetCode 不要求輸出順序，因此測試前先將每個群組和群組列表排序。

import assert from "node:assert/strict";

function normalize(groups: string[][]): string[][] {
  return groups
    .map((group) => [...group].sort())
    .sort((left, right) => left.join(",").localeCompare(right.join(",")));
}

assert.deepStrictEqual(
  normalize(groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"])),
  normalize([["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]),
);
assert.deepStrictEqual(normalize(groupAnagrams([""])), [[""]]);
assert.deepStrictEqual(normalize(groupAnagrams(["a"])), [["a"]]);
assert.deepStrictEqual(
  normalize(groupAnagrams(["abc", "bca", "abc", "xyz"])),
  normalize([["abc", "bca", "abc"], ["xyz"]]),
);

常見陷阱

• 用 map.set(key, [...old, value]) 累積群組。它可讀，但會反覆複製已有陣列。
• 把 map.get(key).push(value) 放進 map.set()。push() 回傳的是數字長度。
• 只用排序後字串的 Set。Set 只能判斷 key 是否出現過，不能保留完整群組。
• 沒有在測試時正規化群組順序。題目允許任意順序，直接比較巢狀陣列可能出現假失敗。
• 對 Unicode 輸入沿用 26 格計數陣列。這個最佳化只適用於題目給的小寫英文字母。

可遷移的思路

當多個資料要依照同一種結構分組時，先找出穩定的 canonical key。字串排序、字元次數、正規化 URL、排序後的 ID 集合都能是 key。key 一旦固定，Map 就能在一次走訪中完成分組。

外部參考連結

• LeetCode 49：Group Anagrams：題目、範例與小寫英文字母限制。
• MDN：Array.prototype.sort()：原地排序與實作相關的複雜度。
• MDN：Map：key-value 語意與存取複雜度要求。
• MDN：Array.prototype.push()：push() 的原地修改行為與新長度回傳值。
• Node.js：assert.deepStrictEqual()：巢狀陣列的嚴格比較。