主題: 學習筆記
LeetCode 125：TypeScript Valid Palindrome，從清理字串到原地雙指標
保留先清理字串的雙指標解法，再說明 charCodeAt 版本如何原地跳過非英數字元。
我一開始先把字串清理成只剩英數字元，再從兩端往中間比。這個做法直觀，也能正確解題。後來看到另一種寫法直接在原字串上跳過符號，才發現差別不在雙指標本身，而是要不要先建立另一份字串。
題目
對應原題：LeetCode 125：Valid Palindrome
給定字串 s，忽略非英數字元與英文大小寫後，判斷它是否為迴文。迴文從左到右和從右到左讀起來相同。
先清理字串的直接做法
這個版本不需要枚舉所有子字串或字元配對，時間本來就是線性。它的代價在於先建立 str，所以額外空間會隨輸入長度成長。
function isPalindromeAfterCleaning(s: string): boolean {
if (s.length === 1) return true;
const str = s.replace(/[^a-zA-Z0-9]/g, "").toLowerCase();
let p1 = 0;
let p2 = str.length - 1;
while (p1 < p2) {
if (str[p1] !== str[p2]) return false;
p1 += 1;
p2 -= 1;
}
return true;
}replace() 移除非英數字元，toLowerCase() 統一大小寫。接著 p1 從左、p2 從右比對。若兩側不同，立刻回傳 false；若都相同，指標相遇後回傳 true。
這裡的迴圈最多比較 str.length / 2 次，但漸近時間仍寫成 O(n)，常數二不會改變 Big O。清理和轉小寫也各會走訪字串，因此總時間是 O(n)。str 是一份新的字串，額外空間為 O(n)。
單一字元的提前回傳可以刪除。空字串或只剩符號的字串在清理後會得到空字串，while 不會執行，最後自然回傳 true。
我後來看到的原地雙指標版本
另一個做法不先清理整份字串。它在每次比較前，讓左右指標各自跳過不需要的字元。
function isAlphanumeric(char: string): boolean {
const lowerCase = char.toLowerCase();
const code = lowerCase.charCodeAt(0);
return (
(code >= "a".charCodeAt(0) && code <= "z".charCodeAt(0)) ||
(code >= "0".charCodeAt(0) && code <= "9".charCodeAt(0))
);
}
function isPalindrome(s: string): boolean {
let left = 0;
let right = s.length - 1;
while (left < right) {
while (left < right && !isAlphanumeric(s[left])) {
left += 1;
}
while (left < right && !isAlphanumeric(s[right])) {
right -= 1;
}
if (s[left].toLowerCase() !== s[right].toLowerCase()) {
return false;
}
left += 1;
right -= 1;
}
return true;
}isAlphanumeric() 只是把「這個字元能不能參與比較」寫成一個明確條件。它先轉成小寫，再用 charCodeAt(0) 判斷是否落在 a 到 z 或 0 到 9 的範圍。這不是需要硬背的雙指標公式，只是不用正規表示式時的一種英數字元判斷方式。
我把重複呼叫的 charCodeAt(0) 存在 code 裡，讓條件更容易讀。這個判斷依賴題目使用可列舉的英文字母和數字；若需求改成完整 Unicode 字母，判斷規則必須重新定義。
左右指標在跳過符號後，才比較兩側字元的大小寫無關形式。每個指標都只會向中間前進，不會倒退，因此每個字元最多被檢查固定次數。時間是 O(n)，且只使用幾個索引與暫存字元，額外空間是 O(1)。
為什麼原地版本正確
每一次真正比較前，left 和 right 都指向尚未處理區間中最外側的英數字元。兩個內層迴圈只跳過題目要求忽略的字元，不會略過任何應比較的字元。
若兩側轉小寫後不同，沒有任何忽略規則可以消除這個差異，字串不是迴文。若相同，兩個字元可以成對移除，剩下的問題仍是較小區間的相同判斷。直到指標相遇為止都沒有衝突，字串就是迴文。
最小驗證
import assert from "node:assert/strict";
assert.strictEqual(isPalindrome("A man, a plan, a canal: Panama"), true);
assert.strictEqual(isPalindrome("race a car"), false);
assert.strictEqual(isPalindrome(" "), true);
assert.strictEqual(isPalindrome("0P"), false);
assert.strictEqual(isPalindrome("a."), true);" " 驗證所有字元都被忽略時的結果。"0P" 則確認數字和字母仍會參與比較。
常見陷阱
- 把
O(n / 2)當成不同的 Big O。它仍是O(n)。 - 宣稱先清理字串的版本是
O(1)空間。新的str需要O(n)空間。 - 用
\w判斷英數字元。它還會接受底線，和題目的英數字元定義不同。 - 直接比較未轉小寫的字元，讓
"A"和"a"被誤判為不同。 - 跳過符號後沒有再次確認
left < right，可能讓索引處理變得難以閱讀。
可遷移的思路
雙指標題不一定要先轉換整份輸入。若規則只影響少數字元，可以在指標前進時即時略過。這能省下額外記憶體，也讓真正的比較規則留在同一個迴圈裡。