主題: 學習筆記

LeetCode 242：TypeScript Valid Anagram，從排序到字元計數

比較排序、Map 計數與固定大小計數陣列，說明 Valid Anagram 的正確性、不變量與複雜度。

這篇先保留我自己寫的排序解與 Map 計數解，再補上後來依題目限制整理出的 26 格計數陣列版本。三個版本都先檢查字串長度，差別在於保留多少額外資料來比較字元次數。

題目

對應原題：LeetCode 242：Valid Anagram

給定兩個只含小寫英文字母的字串 s 和 t。若 t 是 s 的 anagram，回傳 true，否則回傳 false。兩個字串由相同字元且每個字元出現次數相同時，才是 anagram。

暴力解會反覆搜尋字元

function isAnagramBruteForce(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const remaining = t.split("");

  for (const char of s) {
    const index = remaining.indexOf(char);

    if (index === -1) return false;

    remaining.splice(index, 1);
  }

  return true;
}

每次處理 s 的字元，都在剩餘字元中搜尋並刪除一個相同字元。indexOf() 和 splice() 都可能走訪線性數量的元素，總時間是 O(n²)。remaining 另外複製了 t，空間是 O(n)。

我最先寫的排序解法

function isAnagramBySorting(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const sortedS = s.split("").sort().join("");
  const sortedT = t.split("").sort().join("");

  return sortedS === sortedT;
}

長度不同時不可能有相同總數的字元，因此可以直接回傳 false。長度相同時，兩個字串排序後會把相同字元排成相同順序。排序結果相同，就表示字元集合和每個字元的次數都相同。

這是我最先寫出的正確解法。面試通常把比較排序視為 O(n log n)，兩個字串排序後仍是 O(n log n)。split() 和 join() 會建立新資料，因此額外空間是 O(n)。JavaScript 不保證 Array.prototype.sort() 固定使用哪種排序演算法或固定的時間、空間複雜度，所以這裡的 O(n log n) 是演算法面試採用的常見模型，而不是語言規格的保證。MDN 的 sort 文件也明確說明實作決定實際複雜度。

我改良的 Map 次數差解法

function isAnagramByMap(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const counts = new Map<string, number>();

  for (let index = 0; index < s.length; index += 1) {
    const left = s[index];
    const right = t[index];

    counts.set(left, (counts.get(left) ?? 0) + 1);
    counts.set(right, (counts.get(right) ?? 0) - 1);
  }

  return [...counts.values()].every((count) => count === 0);
}

這是我從排序解改良出的版本。它把 s 的字元加一，把 t 同一位置的字元減一。走訪結束後，每個 Map value 都是零，代表兩邊每種字元的次數都抵銷。

不必先把字串展開成 sArr 和 tArr。字串可用索引讀取字元，少掉兩個不必要的陣列複製。面試中通常把 Map 的查詢與更新視為預期 O(1)，因此總時間為預期 O(n)。Map 最多保存 k 種不同字元，額外空間是 O(k)，最壞情況是 O(n)，不是 O(1)。MDN 的 Map 文件說明其平均存取需低於線性時間，但不保證單一固定實作。

後來找到的 26 格計數陣列做法

前兩個版本是我自己寫的解法。原題限定小寫英文字母，字元範圍固定為 26 個，因此後來找到的這個版本不需要 Map，用長度固定的計數陣列就能更省空間。

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false;

  const counts = new Array<number>(26).fill(0);
  const firstLowercaseCode = "a".charCodeAt(0);

  for (let index = 0; index < s.length; index += 1) {
    counts[s.charCodeAt(index) - firstLowercaseCode] += 1;
    counts[t.charCodeAt(index) - firstLowercaseCode] -= 1;
  }

  return counts.every((count) => count === 0);
}

每個字母固定對應一個索引，例如 a 對應 0、z 對應 25。掃描時，一邊加一、一邊減一。陣列只有 26 格，不會隨輸入長度成長，因此時間是 O(n)，額外空間是 O(1)。

這是本題限制下較好的選擇。若字元範圍不是固定的小寫英文字母，例如題目的 Unicode 延伸問題，改用 Map 比較合適。

為什麼計數解正確

在處理完索引 index 後，counts[char] 等於 s[0..index] 中 char 的出現次數，減去 t[0..index] 中 char 的出現次數。

迴圈結束時，每個計數都是零，表示每個字元在兩個字串中出現相同次數，所以兩者是 anagram。只要有一個計數不是零，至少有一種字元的次數不同，答案必定是 false。

複雜度比較

最小驗證

import assert from "node:assert/strict";

assert.strictEqual(isAnagram("anagram", "nagaram"), true);
assert.strictEqual(isAnagram("aasdqqweqw", "qwerw"), false);
assert.strictEqual(isAnagram("cat", "tar"), false);
assert.strictEqual(isAnagram("aa", "a"), false);

第二個案例先驗證長度不同的快速結束。第三個案例長度相同，但字元次數不同，能確認演算法沒有只比較長度。Node.js 的 assert 文件說明 assert.strictEqual() 的嚴格比較行為。

常見陷阱

• 把排序的時間複雜度寫成 O(n²)。一般面試回答使用 O(n log n)，但 JavaScript 規格不承諾實際 sort() 的固定複雜度。
• 把 Map 的時間寫成 O(n log n)。雜湊查詢的面試模型是預期 O(1)，整體才是預期 O(n)。
• 把 Map 的空間寫成 O(1)。字元種類可能隨輸入增加，最壞仍要保存 O(n) 個 key。
• 只檢查字串長度。相同長度不代表每種字元出現次數相同。
• 對 Unicode 輸入直接沿用 26 格陣列。這個最佳化只適用於原題的小寫英文字母限制。

可遷移的思路

兩份資料要比較「每個項目的出現次數」時，可以維護次數差，而不是建立兩份完整的統計結果再比較。這個模式也常出現在字串分組、滑動視窗與頻率統計題。

外部參考連結

• LeetCode 242：Valid Anagram：原始題目、範例與小寫英文字母限制。
• MDN：Array.prototype.sort()：sort() 的原地排序行為與實作相關複雜度。
• MDN：Map：Map 的 key-value 語意與平均存取要求。
• Node.js：assert.strictEqual()：最小 assertions 的嚴格比較。