125. Valid Palindrome

📘 題目敘述

給定一個字串 s，請判斷在把所有非英數字元移除、並將英文字母轉成小寫後，剩下的字串是否為迴文（palindrome）。

若一個字串從左往右讀與從右往左讀都相同，則它是迴文。

條件限制

1 ≤ s.length ≤ 2 * 10^5
s 只包含可列印的 ASCII 字元

🧠 解題思路

我把這題分成兩個階段來做：

第一階段是「先把字串整理成我想比較的樣子」：

把大寫英文字母轉成小寫
保留小寫字母與數字
其他符號（空白、逗號、冒號…）全部刪掉

這樣處理完之後，字串 s 就只剩下 [a-z] 和 [0-9]，可以直接拿來比對。

第二階段才是「判斷是不是迴文」：

我沒有用左右指標直接比
而是把字串後半段倒著接起來形成 pal
再把 s 的前半段拿來和 pal 做字串比較

因為偶數長度與奇數長度的「中心點」處理不同，所以我用 n 的奇偶分開處理。

所有變數

trans：第一階段用來掃描字串的位置指標（逐字處理、同時可能刪字元）
pal：第二階段用來存「反轉後半段」的字串，最後用來和前半段比較
n：整理完後的字串長度，用來判斷奇偶與切割範圍

🪜 主要流程步驟

第一階段：整理字串（只保留英數，字母轉小寫）

我用 trans 從左到右掃描 s，會遇到幾種情況：

情況一：遇到大寫字母 `A`～`Z`

我把它轉成小寫（透過 ASCII 差值）
然後 trans++ 繼續往後走

情況二：遇到數字 `0`～`9`

這些字元本來就要保留
直接 trans++

情況三：遇到小寫字母 `a`～`z`

這些字元也要保留
直接 trans++

情況四：遇到其他字元（符號、空白、標點）

這些字元不應該參與回文判斷
所以我把它從字串中刪掉
刪掉後不做 trans++，因為刪除會讓後面的字元往前補上來，需要繼續檢查同一個索引位置

整理完後，字串 s 就變成只含英數的乾淨版本。

第二階段：判斷是否迴文（用字串切半比較）

整理完後我令 n = s.size()，接著看長度是偶數還是奇數：

情況一：`n` 是偶數

我把後半段反過來接成 pal
然後比較：
- 前半段 s.substr(0, n / 2)
- 是否等於 pal
相等就回傳 true，否則 false

情況二：`n` 是奇數

這時中間那個字元左右對稱時會自己對到自己
我的做法是把「包含中間字元的那一半」也一起放進比較
所以我同樣把後半段反過來接成 pal
然後比較：
- s.substr(0, n / 2 + 1)
- 是否等於 pal
相等就回傳 true，否則 false

💻 程式碼實作

class Solution {
public:
    bool isPalindrome(string s) {
        int trans = 0;
        string pal = "";
        while (trans < s.size()) {
            if (s[trans] >= 'A' && s[trans] <= 'Z') {
                s[trans] = (char)(s[trans] + 'a' - 'A');
                trans++;
            } else if (s[trans] >= '0' && s[trans] <= '9') {
                trans++;
            } else if (s[trans] < 'a' || s[trans] > 'z') {
                s.erase(trans, 1);
            } else {
                trans++;
            }
        }

        int n = s.size();
        if (n % 2 == 0) {
            for (int i = n - 1; i >= n / 2; i--) {
                pal += s[i];
            }
            if (s.substr(0, n / 2) == pal) {
                return true;
            } else {
                return false;
            }
        } else {
            for (int i = n - 1; i >= n / 2; i--) {
                pal += s[i];
            }
            if (s.substr(0, n / 2 + 1) == pal) {
                return true;
            } else {
                return false;
            }
        }
    }
};

🔗 題目連結

https://leetcode.com/problems/valid-palindrome/