LeetCode-125. 驗證回文串

題目來源

125. 驗證回文串

題目詳情

給定一個字元串，驗證它是否是回文串，隻考慮字母和數字字元，可以忽略字母的大小寫。

說明： 本題中，我們将空字元串定義為有效的回文串。

示例 1:

輸入: "A man, a plan, a canal: Panama"

輸出: true

解釋： "amanaplanacanalpanama" 是回文串

示例 2:

輸入: "race a car"

輸出: false

解釋： "raceacar" 不是回文串

提示：

• 1 <= s.length <= 2 * 105

• 字元串

  s

  由 ASCII 字元組成

題解分析

解法一：雙指針法

1. 本題是需要判斷回文串，一看到回文，我們就應該聯想到雙指針法，因為回文的特點就是頭尾字元對應的，也是以可以考慮使用首尾指針來求解。
2. 但是，本題有一個特點就是，這裡并不是所有字元都是有效的，有一些字元是不必要考慮的，是以，在周遊的過程中，需要跳過這些不合法的字元，而隻比較合法的字元。

class Solution {
    public boolean isPalindrome(String s) {
        s = s.trim();
        int n = s.length();
        s = s.toLowerCase();
        int left = 0, right = n-1;
        while(left <= right){
            char chl = s.charAt(left);
            char chr = s.charAt(right);
            if(Character.isLetterOrDigit(chl) && Character.isLetterOrDigit(chr)){
                if(chl != chr){
                    return false;
                }
                left++;
                right--;
            }
            if(!Character.isLetterOrDigit(chl)){
                left++;
            }
            if(!Character.isLetterOrDigit(chr)){
                right--;
            }
        }
        return true;
    }
}
           

Either Excellent or Rusty