在 LeetCode 125 題「Valid Palindrome」中，我們需要判斷一個字串是否為迴文（Palindrome）。迴文的定義是，忽略大小寫字母和非字母數字字元後，該字串正著讀和反著讀是一樣的。

題目：
給定一個字串，判斷它是否為迴文。我們需要忽略非字母數字字元，以及大小寫差異。

範例：

輸入: "A man, a plan, a canal: Panama"
輸出: true
解釋: 忽略非字母數字字元以及大小寫後，字串為 "amanaplanacanalpanama"，它是一個迴文。

解題思路

這道題的核心在於如何有效地過濾掉不必要的字元（例如標點符號、空格等），並且忽略大小寫來進行比較。

我們可以使用「雙指標法」來解決這個問題：

1. 定義兩個指標，一個指向字串的頭部（左指標），一個指向尾部（右指標）。
2. 我們逐一檢查兩個指標指向的字元，如果它們都是有效的字母或數字，則比較它們是否相等。
3. 如果相等，則繼續移動指標：左指標向右移動，右指標向左移動。
4. 如果遇到無效字元（例如標點符號），則跳過這些字元，繼續比較下一個有效字元。
5. 如果在比較過程中有任何不相等的字元，則回傳 false；如果所有字元都相等，則回傳 true。

解法：雙指標法

我們使用雙指標法來遍歷字串，從頭尾兩側向中間收縮，同時忽略非字母數字字元，並且忽略大小寫差異。

實作：

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0; // left
        int j = s.size() - 1; // right
        while (i < j) {
            if (!isalnum(s[i])) {
                i++;
                continue;
            }

            if (!isalnum(s[j])) {
                j--;
                continue;
            }
            
            if (tolower(s[i]) != tolower(s[j])) {
                return false;
            }

            i++;
            j--;
        }
        return true;
    }
};

解題要點

• 要知道有個好用的 isalnum 內建函式，可以檢查是否為字母或數字
• tolower 轉小寫，toupper 轉大寫