迴文是指由前往後讀與由後往前讀都相同的字串,而在標準 C++ 中用來驗證迴文的方式,是一個雙指標迴圈,從字串的兩端往中間走,直到字元不相符或兩指標相遇。該函式接收你的字串,將一個索引設在開頭、另一個設在結尾,然後逐對比較;若每對都相符就回傳 true,否則回傳 false。這個教科書式的模式適用於像 "racecar" 這類單字,以及像 "1881" 這類數字,但真實的迴文題目幾乎都會加上額外的條件:忽略大小寫、去除空白、移除標點符號,有時甚至只保留字母與數字。一旦加入這些規則,你實際用來比較的字串就不再是你原本輸入的字串,這也是為什麼同一個詞組在某個規則下是迴文、在另一個規則下卻不是。了解 C++ 演算法本身以及所套用的確切正規化規則,就能每次都重現出正確的判斷結果。

經典的 C++ 雙指標做法
最常見的 C++ 實作會從索引 0 與索引 size-1 開始,然後讓兩個指標往中間走。在每一步中比較目前的字元,若第一次發現不相符就回傳 false;若兩指標相遇前都沒有不一致的情形,則該字串就是迴文。最精簡的版本看起來像這樣:宣告 left 為 0,right 為 s.size() - 1;當 left < right 時持續迴圈;比較 s[left] 與 s[right];若兩者不同則回傳 false;否則將 left 前進、將 right 後退。當迴圈結束時,回傳 true。其時間複雜度為 O(n),空間複雜度為 O(1),因為原始字串是就地讀取的。
若要做數字檢查,同樣的概念也適用於位數:用 modulo 10 取出最後一位、組合出反向後的數字,再進行比較。當輸入接近 INT_MAX 時要小心帶正負號的溢位問題,為了安全起見建議使用 long long。一種常見的變化是只反轉數字的一半,這樣可以將工作量減半並完全消除溢位風險。以 10 進行整數除法可以讓你在不將數字轉成字串的情況下剝除位數,因此當教學練習中使用 cin >> num 讀取輸入時,位數處理方式通常是最乾淨的選擇。
為什麼規則和程式碼同樣重要
演算法決定了迴圈的執行方式;而規則則決定了怎樣才算「相同的字元」。大多數「檢查迴文」的題目,包括知名的 FreeCodeCamp 挑戰,都會要求你在比較之前先移除非英數字元並將其餘字元轉為小寫。一旦改變規則,判斷結果就可能翻轉。在大小寫折疊規則下,「Aa」是迴文;在嚴格的位元組比較下則不是。移除標點後,「No 'on'」會變成「noon」而成為迴文;但在嚴格比較下則不是。
正因為規則會改變答案,一個有用的習慣是把 C++ 函式分成兩個階段來撰寫:一個負責回傳清理後字串的正規化器,以及一個使用兩個索引走訪清理後字串的檢查器。將步驟分開可以在除錯時印出清理後的字串,這是找出正規化錯誤最快的做法。它也讓你能將正規化器重複用於相關問題,例如計算保留下來的字元數,或比較兩個清理後的字串以進行變位詞風格的檢查。
若你在比較前需要協助移除標點符號,像 Remove Punctuation 這類工具能讓你快速看到一個複雜詞組被清理後的樣貌。在符合常見的「僅保留英數字、轉小寫」規則時,這個可見的清理步驟同樣很有用。
如何用瀏覽器工具驗證你的 C++ 輸出
寫完函式後,你會希望有一個不需要為每組測試詞組重新執行程式就能快速驗證的方法。Palindrome Checker 完全在你的瀏覽器中執行,套用一條明確的正規化原則,並顯示它實際用來比較的字串,讓你能確認你的 C++ 正規化器產生相同的結果。
- 在輸入欄位中輸入單字、詞組、句子或數字。
- 點選執行,並檢視工具所顯示、作為比較基準的正規化後英數字字串。
- 同時閱讀 yes 或 no 的判斷結果以及保留下來的字元數。
- 將工具所標示的正規化方式(小寫、NFKC、僅保留字母與數字、保留變音符號)與你必須遵循的特定比賽規則進行比對。
- 若是較長的測試案例,可貼上最多一百萬個 Unicode 碼位;工具會在本機處理,絕不上傳。
判斷結果與所顯示的正規化字串一致,所以若與你的 C++ 輸出不符,幾乎必定是因為正規化規則不同,而不是邏輯錯誤。最常見的差異來自於:某一處將變音符號移除、另一處卻保留;或某一處將標點視為有意義、另一處則忽略。
這個工具實際比較的內容
檢查器首先會拒絕空輸入、格式錯誤的 UTF-16,以及任何超過一百萬個碼位的輸入。接著套用 Unicode NFKC 正規化,使用固定的英文地區設定進行小寫轉換,並逐個碼位走訪輸入,只保留 Unicode 類別為字母 (Letter) 或數字 (Number) 的字元。空白、標點、符號與表情符號會在此步驟中被剔除。若最後沒有任何字元被保留,工具會回傳明確的錯誤,而不會將空字串判定為迴文。
比較本身是在保留下來的碼位上,從兩端往中間進行,並在第一次不相符時停止。工具並不會反轉原始的 UTF-16 碼元,因此 U+FFFF 以上的輔助字元會保持完整,不會被拆成代理對。帶變音符號的字母會保留在字串中,這代表「Été」會被正規化為「été」,在此規則下被視為迴文。所記錄的範例展示了所公布的原則如何對應常見輸入:
| 輸入 | 正規化後的比較字串 | 工具判斷結果 |
|---|---|---|
| A man, a plan, a canal: Panama | amanaplanacanalpanama | yes |
| race car | racecar | yes |
| 1881 | 1881 | yes |
| Hello | hello | no |
| Été | été | yes |
| !!! | (未保留任何字母或數字) | rejected |
對於較大的輸入,正規化預覽可能會很長,因此工具會將其顯示在一個有邊界的可捲動面板中,並一併顯示精確的保留字元數。判斷結果正是基於該字串所產生,因此你所看到的就是實際比較的內容。
值得了解的輸入限制與邊界情況
當你從真實的 C++ 測試資料將文字餵給檢查器時,有三個限制值得注意。第一個是一百萬個 Unicode 碼位的上限,這遠高於單一教科書練習,足以涵蓋長篇文章,但仍非無限。第二個是要求至少要有一個字母或數字碼位在正規化後存活,這能避免純標點、空白或表情符號組成的字串被標記為空迴文。第三個是缺乏特定語言的轉寫:「Łódź」不會被轉成「Lodz」,希臘字母 Σ 也不會跨文字系統折疊為 sigma;工具只會在大小寫折疊與 NFKC 之後,比較你所輸入的內容,不會多做處理。
當你在比較輸出時,以下兩點相關說明會有所幫助。相容性字元在 NFKC 下可能會塌縮為同一個碼位,因此某些排版上看起來不同的字元對會被視為相等。表情符號會因為公布的「僅限字母與數字」範圍而被排除,而不會被當作比較單位,這代表輸入中的愛心或笑臉會從正規化字串中移除,不會影響判斷結果。
在 C++ 程式與瀏覽器工具之間做選擇
當作業指定了特定規則、當你需要將迴文檢查整合到更大的流程中,或是當輸入必須留在記憶體中而不能離開程式時,你自己寫的 C++ 函式就是合適的工具。當你想要在不寫程式碼的情況下確認某條正規化規則會產生什麼結果、當你需要除錯棘手的 Unicode 案例,或是當你想要一個可以與數字計數一起展示的可重現判斷時,瀏覽器檢查器就是合適的工具。在一般的學習練習中,兩者皆可使用;差別在於你需要的是自行掌控規則,還是只想看到規則被套用的結果。
第二個有用的習慣是,當沒有指定其他規則時,在你的 C++ 程式碼中鏡像工具的策略。使用 std::tolower 進行小寫轉換、以兩個 std::string::size_type 索引走訪字串,並以嚴格相等進行比較。在現代 C++ 中處理與 Unicode 相關的工作時,建議使用 C++20 的 ranges,搭配能濾掉非英數字元的 view,並避免對 UTF-8 進行位元組層級的比較,因為那會切開多位元組的碼位。若有疑慮,請將同一個輸入同時貼進你編譯好的程式以及 Palindrome Checker,並將工具預覽中的正規化字串與你從正規化器印出的清理後字串進行比對;若你的規則是一致的,兩者應該逐字元相符。
若想進一步了解,請參閱 Check for Palindrome GFG: Verify Any Input。
若想進一步了解,請參閱 Check for Palindrome in JavaScript: Methods and Verify。