125. Valid Palindrome

題目 / Problem

中文： 給定一個字串 s，把所有大寫字母轉成小寫，並移除所有非字母與數字（non-alphanumeric）的字元之後，如果剩下的字串從左讀和從右讀完全相同，就稱為回文（palindrome）。請判斷 s 經過上述處理後是否為回文，是則回傳 true，否則回傳 false。

English: A string s is a palindrome if, after lowercasing all letters and removing every non-alphanumeric character, it reads the same forwards as backwards. Alphanumeric characters are letters (a–z, A–Z) and digits (0–9). Return true if s is a palindrome under this rule, false otherwise.

Constraints: - 1 <= s.length <= 2 * 10^5 - s consists only of printable ASCII characters.

Worked example: - Input: s = "A man, a plan, a canal: Panama" - After cleaning: "amanaplanacanalpanama" - Reversed: "amanaplanacanalpanama" — same string → Output: true.

名詞解釋 / Glossary

• Palindrome / 回文：A string that reads the same forwards and backwards, e.g. "aba", "1221". 從左讀和從右讀完全一樣的字串。
• Alphanumeric / 字母數字字元：The 62 characters a–z, A–Z, 0–9. Anything else (space, punctuation, symbols) is non-alphanumeric. C 提供 isalnum() 函式來檢查。
• Two pointers / 雙指針：A technique where two index variables walk through the array/string — usually one from the left and one from the right, moving toward each other. It lets us compare or process pairs in O(n) without extra memory. 比起先建立新字串再比較，雙指針可以原地（in-place）完成檢查。
• In-place / 原地處理：Solving the problem without allocating an additional array/string proportional to the input size. 我們只用幾個 index 變數，不另外配置 O(n) 的記憶體。
• isalnum(c) / tolower(c)：Standard library helpers from <ctype.h> (C) and <cctype> (C++). isalnum returns non-zero if c is a letter or digit; tolower converts an uppercase letter to lowercase (and leaves other characters unchanged). 注意：傳入的字元最好先轉成 unsigned char，否則對某些非 ASCII 值會有 undefined behavior。
• ASCII：A 7-bit character encoding where each character is a number 0–127. 'A' = 65, 'a' = 97，相差 32，所以小寫化也可以用位元運算 c | 32，但本題用 tolower 較清楚。

思路

中文： 最直觀（brute force）的做法是：先用一個迴圈把 s 中所有非字母數字字元濾掉、並把大寫轉成小寫，得到一個乾淨字串 t；接著再把 t 反轉得到 r，比較 t == r。這個做法是對的，但需要額外 O(n) 的空間存 t 和 r，對學習雙指針技巧也沒有幫助。

更好的做法是用雙指針：設 left = 0、right = n - 1，兩個指針同時往中間移動。每次比較前，先讓 left 一直右移、跳過所有非字母數字字元，再讓 right 一直左移、跳過所有非字母數字字元——這樣兩個指針指到的就一定是「有效字元」。然後把兩個字元都轉成小寫並比較：若不相等就立刻回傳 false；若相等就 left++、right--，繼續下一輪。當 left >= right 時，所有對稱位置都檢查完畢，回傳 true。

為什麼這樣是正確的？因為「跳過非字母數字字元」等價於先建立乾淨字串 t，而「比較 t[i] 和 t[n-1-i]」正好就是雙指針在做的事，只是我們不另外開一塊記憶體。時間仍然是 O(n)，但空間降到 O(1)。

English: The brute-force idea is to build a cleaned-up copy of the string — keep only alphanumeric characters, lowercase them — and then check whether that cleaned string equals its reverse. It works but uses O(n) extra space and doesn't teach the core technique this problem is meant to teach.

The optimal approach is two pointers. Start with left = 0 and right = n - 1. On each step, first skip non-alphanumeric characters by advancing left rightwards and right leftwards until both point at valid characters. Then lowercase both characters and compare them. If they differ, the string can't be a palindrome — return false immediately. If they match, move both pointers inwards (left++, right--) and repeat. When left meets or passes right, every symmetric pair has been verified, so return true.

This is correct because skipping non-alphanumeric characters is logically the same as constructing the cleaned string, and comparing characters from both ends is exactly the palindrome check on that cleaned string — we just avoid materializing it. Time stays O(n) (each character is visited at most once by each pointer), and space drops to O(1).

逐步走查 / Walkthrough

Input: s = "A man, a plan, a canal: Panama", length n = 30. Indices 0..29. L = left, R = right.

In total each character is touched at most twice (once when a pointer arrives, once when it leaves), so the work is linear in n.

Solution — C

// Algorithm / 演算法：
//   Two pointers from both ends. Skip non-alphanumeric characters,
//   compare lowercase forms, and shrink inward.
//   雙指針從兩端往中間走，跳過非字母數字，比較小寫後相等就繼續，遇到不等立即回傳 false。
//   Time O(n), Space O(1).

#include <stdbool.h>   // bool, true, false 型別 / boolean type
#include <ctype.h>     // isalnum, tolower 字元判斷與轉換 / char classification helpers
#include <string.h>    // strlen 取得字串長度 / string length

bool isPalindrome(char* s) {
    int left  = 0;                       // 左指針從字串開頭 / left pointer at start
    int right = (int)strlen(s) - 1;      // 右指針從字串結尾 (strlen 不含 '') / right pointer at last char

    while (left < right) {               // 兩指針還沒相遇就繼續 / loop until pointers meet
        // 把 char 轉成 unsigned char 再餵給 isalnum，避免負值造成 undefined behavior
        // Cast to unsigned char before calling isalnum to dodge UB on negative char values
        unsigned char lc = (unsigned char)s[left];
        unsigned char rc = (unsigned char)s[right];

        if (!isalnum(lc)) {              // 左邊不是字母或數字就跳過 / skip non-alnum on the left
            left++;                      // 左指針右移 / advance left pointer
            continue;                    // 重新進入迴圈、重新檢查 / restart the loop iteration
        }
        if (!isalnum(rc)) {              // 右邊不是字母或數字就跳過 / skip non-alnum on the right
            right--;                     // 右指針左移 / advance right pointer
            continue;                    // 重新進入迴圈 / restart
        }

        // 兩邊都是有效字元，統一轉小寫再比較 / both sides valid → lowercase then compare
        if (tolower(lc) != tolower(rc)) {
            return false;                // 一旦不相等就不可能是回文 / mismatch → not a palindrome
        }

        left++;                          // 這一對相等，左指針往內走 / matched pair, move inwards
        right--;                         // 右指針往內走 / move right pointer inwards
    }

    return true;                         // 全部對稱位置都通過檢查 / every symmetric pair matched
}

Solution — C++

// Algorithm / 演算法：
//   Identical two-pointer approach: skip non-alphanumeric characters from
//   both ends, compare lowercase forms, shrink inward.
//   做法與 C 版相同：雙指針 + 跳過非字母數字 + 小寫比較。
//   Time O(n), Space O(1).

#include <string>      // std::string 字串型別 / std::string type
#include <cctype>      // std::isalnum, std::tolower 字元工具 / char helpers

class Solution {
public:
    bool isPalindrome(std::string s) {
        int left  = 0;                            // 左指針 / left index
        int right = static_cast<int>(s.size()) - 1; // 右指針，s.size() 回傳長度 / right index; size() returns length

        while (left < right) {                    // 還沒交會就繼續 / loop until pointers cross
            // 用 unsigned char 包裝再傳入 isalnum/tolower，避免負值 UB
            // Wrap in unsigned char to avoid UB with negative char values
            unsigned char lc = static_cast<unsigned char>(s[left]);
            unsigned char rc = static_cast<unsigned char>(s[right]);

            if (!std::isalnum(lc)) {              // 左非字母數字就跳過 / skip non-alnum on the left
                ++left;                           // 前置 ++ 與後置 ++ 在這裡效果相同 / prefix ++ here
                continue;                         // 進入下一輪迴圈 / next iteration
            }
            if (!std::isalnum(rc)) {              // 右非字母數字就跳過 / skip non-alnum on the right
                --right;                          // 右指針左移 / move right inward
                continue;
            }

            // 兩邊都是有效字元 → 比較小寫 / both valid → compare lowercase
            if (std::tolower(lc) != std::tolower(rc)) {
                return false;                     // 不相等 → 不是回文 / mismatch → not palindrome
            }

            ++left;                               // 配對成功，往中間收 / matched, shrink window
            --right;
        }

        return true;                              // 所有對稱位置皆相等 / all symmetric pairs matched
    }
};

複雜度 / Complexity

• Time: O(n) — Each index in s is visited at most once by left (it only moves right) and at most once by right (it only moves left). The total number of pointer moves is therefore bounded by n, where n = s.length. 每個字元最多被左、右指針各碰過一次，總共線性時間。
• Space: O(1) — We only allocate a constant number of local variables (left, right, two unsigned char temporaries). No extra string is built. 沒有額外配置 O(n) 的字串或陣列。

Pitfalls & Edge Cases

• Passing a raw char to isalnum / tolower is UB on negative values / 直接把 char 傳給 isalnum 可能造成 undefined behavior：On many platforms char is signed, so a byte with value 0x80–0xFF becomes a negative int. The standard says these functions require a value in [0, UCHAR_MAX] or EOF. Always cast to unsigned char first — the solutions do exactly that.
• Empty / all-non-alphanumeric string / 空字串或全是符號的字串：e.g. " ". The loop condition left < right immediately fails (or quickly becomes false after skipping), and we correctly return true. 不需要特別判斷。
• Off-by-one with right / right 的初值：right must start at strlen(s) - 1 (or s.size() - 1), not strlen(s). Using the length itself would read the '\0' terminator (C) or go out of bounds (C++).
• Forgetting to skip on BOTH sides before comparing / 忘記兩邊都要跳過非字母數字：If you skip only on the left, characters like "," on the right could be wrongly compared against a letter on the left and return false incorrectly. The two separate if blocks with continue guarantee both pointers land on valid characters before any comparison.
• continue vs falling through / continue 的用意：After moving a pointer past a non-alnum character, we want to re-check the loop condition (the new s[left] might also be non-alnum, or left might now exceed right). continue returns to the top of the while, which handles both cases cleanly.
• Digit comparison / 數字也要算：'0'..'9' are alphanumeric too. tolower('5') simply returns '5', so the same code path works for digits — no special case needed.