剑指 Offer II 019. 最多删除一个字符得到回文

题目描述

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

示例 1：

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

示例 2：

输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符

示例3：

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

提示:

• 1 <= s.length <= 105
• s 由小写英文字母组成

思路解析

1.回文串升级版

2.需要进行贪心,如果两边不相等的时候,我们有一次机会去删除一个字符,那么再继续比较l+1到r之间是不是回文或者l到r-1之间是不是回文

代码实现

class Solution {
    public boolean validPalindrome(String s) {
        char[] chars = s.toCharArray();
        int left = 0,right = chars.length-1;
        int cnt = 1;
        while(left<right) {
            if(chars[left]!=chars[right]) {
                return isEcho(chars,left+1,right)||isEcho(chars,left,right-1);
            }
            left++;
            right--;
        }
        return true;
    }
    public boolean isEcho(char[] chars,int l ,int r) {
        while(l<r) {
            if(chars[l]!=chars[r]) return false;
            l++;
            r--;
        }
        return true;
    }
}

欢迎大佬们关注小弟的博客https://blog.csdn.net/qq_41522089