LeetCode Valid Palindrome：雙指針判斷回文串（忽略非字母數字、大小寫）

問題描述

給定一個字符串，驗證它是否為回文串。只考慮字母數字字符，忽略大小寫。空字符串視為有效回文。

核心算法：雙指針原地判斷

1. 左指針 l=0，右指針 r=s.length()-1。
2. 當 l < r：
   • 若 s[l] 非字母數字，l++ 繼續。
   • 若 s[r] 非字母數字，r-- 繼續。
   • 比較 tolower(s[l]) 和 tolower(s[r])，不等返回 false。
   • l++, r--。
3. 循環結束返回 true。

關鍵代碼 (C++)

bool isPalindrome(string s) {
    int l = 0, r = s.size() - 1;
    while (l < r) {
        if (!isalnum(s[l])) { l++; continue; }
        if (!isalnum(s[r])) { r--; continue; }
        if (tolower(s[l]) != tolower(s[r])) return false;
        l++; r--;
    }
    return true;
}

關鍵庫函數

• isalnum(c)：判斷是否字母或數字（<cctype>）。
• tolower(c) / toupper(c)：大小寫轉換。

複雜度分析

• 時間：O(n) — 每字符最多訪問一次。
• 空間：O(1) — 原地雙指針，無額外空間。

邊界情況

• 空串、全非字母數字串 → 返回 true。
• 單字符 → true。
• 大小寫混合如 "A man, a plan, a canal: Panama" → true。

總結

Valid Palindrome 是雙指針技巧的入門題。關鍵在於「跳過非法字符」與「統一大小寫比較」的邏輯順序。同類技巧廣泛用於「字符串去噪比較、子序列匹配」等問題。