在這里插入圖片描述

1，雙指針解決

“回文串”是一個正讀和反讀都一樣的字符串，也就是說他是左右兩邊對稱的。驗證一個字符串是否是回文串，最簡單的一種方式就是使用兩個指針，一個從前開始，一個從后開始，兩個指針同時往中間走，如果他們指向的字符不一樣，那么這個字符串肯定不是回文字符串，直接返回false即可，如果這兩個指針相遇了，直接返回true。

但這題只需要判斷字母和數(shù)字，因為字符串中可能含有其他字符，我們只需要跳過即可，畫個圖來看下

在這里插入圖片描述

最后再來看下代碼

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        //left是左指針，如果不是字母和數(shù)字要過濾掉
        while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
            left++;
        //right也一樣，如果不是字母和數(shù)字也要過濾掉
        while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
            right--;
        //然后判斷這兩個字符是否相同，如果不相同直接返回false，這里是先把字符全部轉(zhuǎn)化為小寫
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
            return false;
        //如果left和right指向的字符忽略大小寫相等的話，這兩個指針要分別往中間移一步
        left++;
        right--;
    }
    //如果都比較完了，說明是回文串，返回true
    return true;
}

我們還可以在比較之前字母全部轉(zhuǎn)化為小寫，這里改為for循環(huán)的方式，只不過是換湯不換藥，原理還都是一樣的，來看一下

public boolean isPalindrome(String s) {
    //先轉(zhuǎn)為小寫
    s = s.toLowerCase();
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        while (i < j && !Character.isLetterOrDigit(s.charAt(i)))
            i++;
        while (i < j && !Character.isLetterOrDigit(s.charAt(j)))
            j--;
        if (s.charAt(i) != s.charAt(j))
            return false;
    }
    return true;
}

2，遞歸方式解決

上面代碼還可以寫成遞歸的方式，無論怎么變，核心思路還是沒變，可以參考一下，代碼如下

public boolean isPalindrome(String s) {
    return isPalindromeHelper(s, 0, s.length() - 1);
}

public boolean isPalindromeHelper(String s, int left, int right) {
    if (left >= right)
        return true;
    while (left < right && !Character.isLetterOrDigit(s.charAt(left)))
        left++;
    while (left < right && !Character.isLetterOrDigit(s.charAt(right)))
        right--;
    return Character.toLowerCase(s.charAt(left)) == Character.toLowerCase(s.charAt(right))
            && isPalindromeHelper(s, ++left, --right);
}