题目

Input: "abca"
Output: True
Explanation: You could delete the character 'c'.

题目描述：可以删除一个字符，判断是否能构成回文字符串。
https://leetcode-cn.com/problems/valid-palindrome-ii/description/

分析

所谓的回文字符串，是指具有左右对称特点的字符串，例如 "abcba" 就是一个回文字符串。

使用双指针可以很容易判断一个字符串是否是回文字符串：令一个指针从左到右遍历，一个指针从右到左遍历，这两个指针同时移动一个位置，每次都判断两个指针指向的字符是否相同，如果都相同，字符串才是具有左右对称性质的回文字符串。

本题的关键是处理删除一个字符。在使用双指针遍历字符串时，如果出现两个指针指向的字符不相等的情况，我们就试着删除一个字符，再判断删除完之后的字符串是否是回文字符串。

在判断是否为回文字符串时，我们不需要判断整个字符串，因为左指针左边和右指针右边的字符之前已经判断过具有对称性质，所以只需要判断中间的子字符串即可。

在试着删除字符时，我们既可以删除左指针指向的字符，也可以删除右指针指向的字符。

代码

正确

 public boolean validPalindrome(String s) {
        char[] str = s.toCharArray();
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (str[i] != str[j]) {
                return isPalindrome(str, i + 1, j) || isPalindrome(str, i, j - 1);//分支
            }
        }
        return true;//如果没有分支
    }
    private boolean isPalindrome(char[] str, int i, int j) {
        while (i < j) {
            if (str[i++] != str[j--]) {//注意 j-- 不小心打错饿了
                return false;
            }
        }
        return true;
    }

反思

错误解法
思路有问题,考虑的不全 很暴力 红了五次 出一次bug 修复一下,,
致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
ebcbb ececabbacec bbcbe
删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】 如正解

public boolean error_validPalindrome(String s) {
        char[] str = s.toCharArray();
        int i = 0, j = s.length() - 1;
        boolean flag = true;
        while (i <= j) {
            if ((str[i] == str[j])) {
                i++;
                j--;
            } else if (flag) { //致命问题 只知道当前这一步 和下一步可以成功 但是后续的能否成功不知道 万一 第一个if的是 后续的不回文 第二个的是回文就糟糕了
                //ebcbb ececabbacec bbcbe   删除 e c都可以 先判断的就可能是死路 所以【在删除之后 重新当做的字符串开始判断】
                if (j - 1 >= i && str[i] == str[j - 1]) {//可以删去
                    i++;
                    j -= 2;
                    flag = false;
                } else if (i + 1 <= j && str[i + 1] == str[j]) {//i删去
                    j--;
                    i += 2;
                    flag = false;
                } else
                    return false;
            } else {
                return false;
            }
        }
        return true;
    }