題目
#

leetcode 125 - Valid Palindrome (題目說明請點連結)

題目簡述
#

判斷一個字串是否為有效的回文。

範例
#

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: 移除所有非字母數字字符後得到 "amanaplanacanalpanama"，這是回文字符串。

Example 2:

Input: s = "race a car"
Output: false
Explanation: 移除所有非字母數字字符後得到 "raceacar"，這不是回文字符串。

Example 3:

Input: s = " "
Output: true
Explanation: 空字符串被認為是回文字符串。

解題思路
#

這題要求我們判斷一個字符串是否為回文字符串。回文字符串是指正著讀和倒著讀都一樣的字符串。我們需要忽略大小寫和非字母數字字符。

解法
#

雙指針法（Two Pointers Approach）

先對字符串進行預處理，轉換為小寫並移除所有非字母數字字符
使用左右兩個指針從兩端向中間移動
比較對應位置的字符是否相同

步驟
#

預處理階段：
- 將字符串轉換為小寫
- 使用正則表達式移除所有非字母數字字符
雙指針比較：
- 初始化 left = 0，right = s.length() - 1
- 當 left < right 時，比較 s.charAt(left) 和 s.charAt(right)
- 如果不相同，返回 false
- 移動指針：left++，right--
最終結果：
- 如果所有字符都相同，返回 true

例子說明
#

s = "A man, a plan, a canal: Panama"

預處理：
- 轉換為小寫："a man, a plan, a canal: panama"
- 移除非字母數字："amanaplanacanalpanama"
雙指針比較：
- left = 0，right = 19
- 比較 'a' 和 'a'：相同，left++，right--
繼續比較：
- left = 1，right = 18
- 比較 'm' 和 'm'：相同，left++，right--
中間相遇：
- 當 left >= right 時，停止比較
- 所有字符都相同，返回 true

完整程式碼
#

java

class Solution {
    public boolean isPalindrome(String s) {
        // 將字符串轉換為小寫，並移除所有非字母數字字符
        s = s.toLowerCase().replaceAll("[^a-z0-9]", "");

        // 初始化左右指針
        int left = 0, right = s.length() - 1;

        // 使用雙指針從兩端向中間移動，比較對應位置的字符
        while(left < right){
            // 如果左右指針指向的字符不同，則不是回文字符串
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            // 移動指針
            left++;
            right--;
        }

        // 如果所有字符都相同，則是回文字符串
        return true;
    }
}