验证回文串Ⅱ

给你一个字符串 s，最多可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

输入：s = "aba"
输出：true

输入：s = "abca"
输出：true
解释：你可以删除字符 'c'。

方法：递归

算法思路：

构造判断是否为回文串方法isPalindrome，使用双指针法
对字符串进行双指针遍历，如果双指针所指的字符不同，则判断去除当前指针位置字符（左指针或右指针）的后续字符串是否为回文串

代码实现：

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;
    }

    public boolean isPalindrome(String s, int i, int j){
        while(i < j){
            if(s.charAt(i) != s.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

复杂度分析：

时间复杂度： $O(n)$ ，其中 $n$ 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 $O(n)$ ，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是 $O(n)$ 。

空间复杂度： $O(1)$ 。只需要维护有限的常量空间。

参考

LeetCode 题解 - 双指针｜CS-Notes