LeetCode/680. 验证回文字符串 Ⅱ

680. 验证回文字符串 Ⅱ

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

示例1:

输入: "aba"
输出: True

示例2：

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

注意:

1. 字符串只包含从 a-z的小写字母。字符串的最大长度是50000。

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题解：

本题和125. 验证回文串很像，除去了标点符号和大小写，但是增加了可以删除一个元素的条件。我们还是创建双指针，这里我们选择将字符串s转换为char[]数组，这样能够提高速度。left指针向前遍历，right指针向后遍历，因为题目说了允许删除一个字符来构成回文字符串，所以我们在遇到第一个不是回文的两个字符后，可以通过isValidPalindrome方法判断夹在left和right之间的子串是不是回文子串。这样，当遇到第一组不相同的字符后，我们进入isValidPalindrome判断，如果子串继续不相同，那么就不是回文字符串，如果相同就是。

具体代码如下：

class Solution {
    public boolean validPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        char[] chars = s.toCharArray();
        while (left < right) {
            if (chars[left] != chars[right])
                //如果两个子串有一个不是回文子串，那么该字符串就不是回文字符串
                return isValidPalindrome(chars, left + 1, right) || isValidPalindrome(chars, left, right - 1);
            left++;
            right--;
        }
        return true;
    }

    private boolean isValidPalindrome(char[] chars, int left, int right) {
        while (left < right) {
            if (chars[left++] != chars[right--])
                return false;
        }
        return true;
    }
}