给定一个非空字符串 s
,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
输入: s = "aba" 输出: true
输入: s = "abca" 输出: true 解释: 可以删除 "c" 字符 或者 "b" 字符
输入: 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