[leetCode]680. 驗證回文字元串 Ⅱ

題目

連結：https://leetcode-cn.com/problems/valid-palindrome-ii

給定一個非空字元串 s，最多删除一個字元。判斷是否能成為回文字元串。

示例 1:

輸入: "aba"
輸出: True
示例 2:

輸入: "abca"
輸出: True
解釋: 你可以删除c字元。
注意:

字元串隻包含從 a-z 的小寫字母。字元串的最大長度是50000。
           

雙指針

使用雙指針一個從左向右周遊，一個從右向左周遊，判斷兩個指針所指向的字元是否相等，如果不等則判斷删除一個字元（左邊或者右邊）後是否是回文串。删除字元的操作可以使用指針移動完成，删除字元後不需要判斷整個字元串是否是回文串，隻需要判斷子串是否為回文串

class Solution {
    public boolean validPalindrome(String s) {
        for (int i = 0, j = s.length() - 1 ; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
            }
        }
        return true;
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}