在 JavaScript 中,當一個字串在經過文件化的標準化步驟(移除空格、標點符號以及大小寫差異)後,其保留的字母與數字正著讀與反著讀完全相同,該字串就是迴文。Merriam-Webster 的定義用具體例子為這個熟悉的概念提供了依據,從 dad 和 1881,到 race car 以及 A man, a plan, a canal: Panama 等詞組,皆在忽略大小寫與標點的情況下正讀反讀皆相同。實際上,多數 JavaScript 迴文檢查並非依賴原始的字元逐一相等,因為真實世界的輸入混雜著大寫字母、空格、逗號以及 Unicode 字元,使單純的比較變得複雜。因此,一個可用的檢查會先標準化輸入(轉為小寫、去除非字母字元),再將產生的字串與其反轉後的版本相比,或從兩端各以一個索引向中央走,直到發現不符為止。了解你的程式碼採用何種標準化規則,正是區分「一個會判斷 racecar 為迴文」與「一個因為尾端空格或重音字元而靜默回傳 false」的函數之間的差異。本文的其餘部分將逐步介紹兩種可靠的 JavaScript 方法,並展示 迴文檢查工具 如何將其標準化後的字串公開,讓你能以獨立結果驗證自己的實作。

check for palindrome javascript
在 JavaScript 中檢查迴文:方法與驗證

什麼讓一個字串在 JavaScript 中成為迴文

Merriam-Webster 字典條目將迴文定義為「一個單字、詩句或句子……正讀反讀皆相同」。同一來源蒐集了從簡單的 dad 與 1881,到著名句子 A man, a plan, a canal: Panama 等例子,後者僅在你捨棄空格、逗號與冒號之後才具有迴文性質。這個「在你捨棄之後」的子句就是整個標準化政策,也是大多數自行撰寫的 JavaScript 函數出錯的地方。

在 JavaScript 中,字面值字串 "A man, a plan, a canal: Panama" 由於首尾字元不同,純粹的相等性測試就已失敗。因此一個可用的函數會先用 toLowerCase() 將其轉為小寫,再用像 /\W/g 這樣的正規表示式去除所有非字母或非數字的字元,接著詢問保留下來的字串反讀是否相同。在此情況下保留的字串正為 amanaplanacanalpanama,這是已知的 Merriam-Webster 例子。JavaScript 字串是 UTF-16 程式碼單位的序列,而非 Unicode 程式碼點,這在輸入包含表情符號或位於基本多文種平面之外字元時便至關重要。在選擇以下兩種方法時,都應將此區別納入考量。

兩種可靠的 JavaScript 迴文方法

第一種方法是反向比較。你透過 split("") 將標準化字串依每個字元切開,用 reverse() 反轉該陣列,再用 join("") 重新組合,建立標準化字串的第二份副本。迴文判定即為原始標準化字串與反轉副本的嚴格相等性。此模式在教學中最為常見,因為它讀來如同英文且夠短能在一行內寫完,但它會額外配置一個陣列與第二個字串,且作用於 UTF-16 程式碼單位上。第二點正是為什麼包含表情符號或輔助平面字元的字串可能產生驚人結果的原因:像 😀 這樣的單一表情符號佔據兩個 UTF-16 單位,而反轉陣列會將那兩半以錯誤的順序排列。

第二種方法是雙指標走訪。在相同的標準化步驟之後,你保留兩個索引,一個從 0 開始,另一個從 length 減 1 開始,並在一個迴圈中比較兩個位置的字元,該迴圈遞增左索引、遞減右索引,直到兩者在中央相遇。當兩個字元首次不同時,函數回傳 false;若迴圈完成且無不符,則回傳 true。這個方法使用 O(1) 的額外記憶體,並在首次不符時即停止,因此平均而言可比反向比較更早給出判定。其缺點在於標準的字串字元存取運算子仍回傳 UTF-16 單位,因此在意輔助字元時,程式碼點安全版本會使用 codePointAt 而非 charAt。

兩種方法共享相同的前三個具體步驟,而這正是大多數兩個實作之間產生分歧的源頭:將整個字串轉為小寫、定義何者算作字母或數字,並套用該篩選器以產生比較字串。選擇 /\W/g 作為篩選器僅去除非單字字元(因此底線會保留);在轉為小寫後選擇 /[^a-z0-9]/gi,則能在明確控制字母表的情況下達到相同效果。篩選器的選擇是一項標準化政策,而非比較演算法,且改變篩選器會改變像 "No 'x' in Nixon" 這類輸入的判定,卻無須更動任何一個比較步驟。

使用迴文檢查工具驗證你的 JavaScript 邏輯

一旦你的函數回傳判定,最快的確認方式是將其與一個會展示運算過程的獨立檢查工具進行比對。迴文檢查工具採用一項明確的標準化政策,顯示它所建立的精確比較字串,並回報保留字元數,讓你能以手工或撰寫小腳本來重現其判定。處理過程在瀏覽器本地執行,因此你可以從測試套件貼上片段而無須上傳任何內容。

  1. 在輸入區中輸入要測試的單字、詞組、句子或數字;該檢查工具接受最多一百萬個 Unicode 程式碼點的文字。
  2. 執行檢查工具並讀取其在比較預覽中顯示的標準化字母與數字字串;這正是判定所依據的精確字串。
  3. 將該保留字串及其字元數與你自己 normalize 函數的輸出進行比較,再讀取 yes 或 no 判定,確認其與你的 JavaScript 程式碼所回傳的結果一致。

若字串相符且判定一致,則你的標準化政策與該檢查工具在該輸入上等價。若兩者不同,差異幾乎皆在於篩選器而非比較迴圈,而預覽字串便是最迅速找出你函數漏掉或保留了哪些字元的方式。

破壞天真 JavaScript 迴文實作的標準化規則

JavaScript 迴文函數回傳錯誤答案最常見的原因,在於標準化步驟不完整或隱藏在比較迴圈之內。空格與標點是顯而易見的情況:"race car" 含有必須在反轉前移除的空格,而嚴格的逐字元檢查器會將該詞組標記為非迴文。迴文檢查工具的公開規則忽略空格、標點、符號與表情符號,同時保留 Unicode 字母與數字,套用 NFKC 標準化,並以固定的英文地區設定轉為小寫。為了讓判定一致,你的程式碼需要鏡像的就是這整句話所描述的政策。

重音字母是常見的靜默失敗。單字 Été 在轉為小寫後變成 "été",在該工具所使用的程式碼點比較下仍是迴文,但一個試圖先去除重音的篩選器會將其變為 "ete",雖然理由錯誤仍得到正確答案。一個因為 "É" 超出 ASCII 範圍而將其視為非字母的篩選器,則會完全丟棄該字元,並在應該為迴文的值上回傳 false。最安全的方式是將重音字母保留原樣,先以 NFKC 標準化字串,再套用你的字母或數字篩選器,使附加於基礎字母上的組合附加記號能可預測地塌縮,而不改變比較結果。

表情符號與輔助字元是最棘手的情況。像露齒笑臉表情符號這樣的單一字元佔據兩個 UTF-16 程式碼單位,而 split("") 會將那兩半作為獨立的陣列項目回傳。反向比較函數接著會將這兩半以錯誤順序排列,並在來源字串僅含該單一表情符號時仍回報迴文不符,這也是為什麼該工具要求至少一個保留的字母或數字,而非將空結果視為迴文的原因。以 codePointAt 按程式碼點迭代,或在帶有 /u 旗標的正規表示式中直接與 Unicode 屬性跳脫(如 \p{Letter} 與 \p{Number})進行值比對,皆能完全避開代理對拆分的問題。若你發現你的函數對含有你本想排除的表情符號的字串回報迴文判定,問題幾乎必定出在篩選器如何處理 U+FFFF 以上的程式碼點。

迴文方法一覽

下表將上述兩種 JavaScript 方法與瀏覽器工具進行比較,聚焦於開發者實際需要推理的差異。表格中引用的數字與政策為該方法的屬性,並非執行任何特定輸入所產生的數值。

面向 JavaScript 中的反向比較 JavaScript 中的雙指標 迴文檢查工具
比較形式 原始字串與反轉副本之間的相等性 從兩端對稱走訪至中央 在標準化預覽上對稱走訪
時間複雜度 O(n) O(n) 最壞情況,通常為 O(n/2) O(n)
額外記憶體 一份反轉副本 O(1) 一份標準化預覽字串
迭代單位 UTF-16 程式碼單位(split/reverse/join) 預設為 UTF-16 程式碼單位,使用 codePointAt 時為程式碼點 Unicode 程式碼點
標準化是否公開 隱藏在函數內部 隱藏在函數內部 以精確的保留字元字串形式顯示
結果 布林值 true 或 false 布林值 true 或 false 布林判定加上保留字元數與預覽

舉例而言,7 個字元的單字 racecar 在雙指標迴圈中需要恰好 floor(7/2) = 3 次對稱配對比較:位置 0 對位置 6,接著 1 對 5,再來 2 對 4,之後位置 3 為中央,迴圈終止並給出迴文判定。相同的輸入在反向比較方法下則會配置一份 7 字元的反轉副本,並對兩個字串進行嚴格相等性測試。這些都是演算法的屬性,而非本文為此而計算的輸出。

當你的 JavaScript 函式與工具結果不一致時

你的程式碼與工具之間的意見分歧是一種訊號,而非錯誤回報。首先要檢查的是篩選條件:你的函式是否移除了工具保留的字元,或是保留了工具移除的字元?常見的兇手包括底線,因為 /\W/g 會保留底線字元,而經過小寫轉換後的 /[^a-z0-9]/ 則會將它們移除;另一個是使用非 ASCII 數字的語言中的數字,這些數字會在比較執行前被 NFKC 正規化改寫為 ASCII 數字。第二個要檢查的地方是比較方向:以 split("").reverse().join("") 建立的反向比較函式,可能會在不知不覺中以錯誤的順序反轉含有組合標記的字串,而對稱走查則無論字串如何建構,都會比較相同的兩個位置。

如果你在完成這些檢查後,程式碼與工具仍然不一致,問題通常出在政策而非程式碼。一個要求嚴格逐字元比對(包括空格與大小寫)的回文題目,會產生與「回文檢查器」公開規則不同的判定結果,而這樣的結果是刻意設計的。當規則明確陳述且比較字串可見時,判定結果可以手動重現;當規則被隱藏時,相同的輸入可能在一個工具中回傳 yes,在另一個工具中回傳 no。一個實用的習慣是撰寫你的正規化函式,使其在回傳布林值的同時也回傳比較字串,然後將該字串貼到工具中確認兩者相符。如果你想使用同一邏輯的編語言版本來擴展測試範圍,在 C++ 中檢查回文:演算法與驗證 指南會逐步介紹另一種語言中的對應走查,有助於交叉檢查你在 JavaScript 中所做的正規化選擇。