LeetCode 125：驗證回文字符串（雙指針優化）

題目描述

給定一個字符串，僅考慮字母數字字符且忽略大小寫，判斷是否為回文。空字符串視為有效回文。

基礎解法：過濾後雙指針

先構建只含字母數字的新字符串並統一轉為大寫，然後雙指針從兩端向中間比較。

class Solution {
public:
    bool isPalindrome(string s) {
        string filtered;
        for (char c : s) {
            if (isalnum(c)) filtered += toupper(c);
        }
        int l = 0, r = filtered.size() - 1;
        while (l < r) {
            if (filtered[l++] != filtered[r--]) return false;
        }
        return true;
    }
};

進階解法：原地雙指針

不額外構建字符串，直接在原字符串上雙指針跳過非字母數字字符，比較時統一轉大寫。空間複雜度 O(1)。

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while (l < r) {
            while (l < r && !isalnum(s[l])) ++l;
            while (l < r && !isalnum(s[r])) --r;
            if (toupper(s[l]) != toupper(s[r])) return false;
            ++l; --r;
        }
        return true;
    }
};

複雜度對比