597，双指针解验证回文字符串 Ⅱ

Original 博哥数据结构和算法 2022-05-19

问题描述

来源：LeetCode第680题

难度：简单

给定一个非空字符串s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

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

示例 2:

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

示例 3:

输入: s = "abc"
输出: false

提示:

1 <= s.length <= 10^5
s 由小写英文字母组成

双指针解决

如果只是验证是否是回文串，这个比较简单，之前也讲过497，双指针验证回文串。但这道题如果不是回文串，我们还可以删除一个字符，判断是否是回文的。

原理还和497题一样，使用两个指针left和right，从字符串的两边相向而行，如果两个指针指向的字符不相同，说明不能构成回文串，我们可以删除一个。可以删除left指向的字符也可以删除right指向的字符，如下图所示

原理比较简单，就不在过多介绍，我们直接看下代码。

public boolean validPalindrome(String s) {
    //左指针
    int left = 0;
    //右指针
    int right = s.length() - 1;
    while (left < right) {
        //如果两个指针指向的字符不一样，我们要删除一个，要么
        // 删除left指针指向的值，要么删除right指针指向的值
        if (s.charAt(left) != s.charAt(right)) {
            return isPalindromic(s, left + 1, right)
                    || isPalindromic(s, left, right - 1);
        }
        left++;
        right--;
    }
    return true;
}

//判断子串[left,right]是否是回文串
private boolean isPalindromic(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left++) != s.charAt(right--)) {
            return false;
        }
    }
    return true;
}