剑指OfferII019 最多删除一个字符得到回文

题目：

思路：

暴力破解,因为只让替换一个字符，我们双指针扫描的时候如果发现对不上，就先跳过让count=1,下次如果对不上并且count=1的时候,就返回false

但是

代码：

class Solution {
    public static boolean validPalindrome(String s) {
          int left = 0,right = s.length()-1;
          int count = 0;


        while (left<right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }else{
                 if (s.charAt(left)==s.charAt(right-1)&&count==0){
                    left++;
                    right-=2;
                    count++;
                }
                else if (s.charAt(left+1)==s.charAt(right)&&count==0){
                    left+=2;
                    right--;
                    count++;
                }else {
                    return false;
                }
            }
        }
        return true;
    }
}

分析：

对于以上问题，在

   if (s.charAt(left)==s.charAt(right-1)&&count==0){
                    left++;
                    right-=2;
                    count++;
                }
                else if (s.charAt(left+1)==s.charAt(right)&&count==0){
                    left+=2;
                    right--;
                    count++;
                }else {
                    return false;
                }

会率先进入一个选择,会返回left和right的一个成功或失败的情况，但是我们希望的情况是left和right有一个成功就可以了，但是上述代码并不能满足要求

优化：

思路：

我们进行递归，在递归的时候只**需Palindrome(left+1)或者Palindrome(right)**返回一个正确就可以了

代码：

class Solution {
    
    public static boolean validPalindrome(String s) {

        int count = 0;
        for (int left = 0,right = s.length() - 1;left<right ; left++,right--) {
               if (s.charAt(left)!=s.charAt(right)){
                   return Palindrome(s,left+1,right)||Palindrome(s,left,right-1);
               }
        }
        return true;
    }
    public static boolean Palindrome(String s ,int left,int right){
        //因为值允许一次,所以在前面我们已经判断了
        while (left<right){
            if (s.charAt(left++)!=s.charAt(right--)){
                return false;
            }
        }
            return true;

    }
}