验证回文字符串 Ⅱ
680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: s = "aba" 输出: true
示例 2:
输入: s = "abca" 输出: true 解释: 你可以删除c字符。
示例 3:
输入: s = "abc" 输出: false
解题思路
对于判断回文字符串我们可以定义左右指针，初始时分别指向字符串的第一个字符和最后一个字符，每次判断左右指针指向的字符是否相同，如果不相同，则不是回文串；如果相同，则将左右指针都往中间移动一位，直到左右指针相遇，则字符串是回文串。
在这题里面，我们根据这个思路，当遇到不匹配的两个字符时，我们可以尝试两个字符都删除一次以后，遍历剩余的字符串查看是否能组成回文字符串，如果还是不行，说明删除一个字符并不能使得字符串变为回文
代码
class Solution { public boolean validPalindrome(String s) { int l=0,n=s.length(),r=n-1; while(l<r) { if(s.charAt(l)!=s.charAt(r)) { return toVlidPalindrome(s,l+1,r)||toVlidPalindrome(s,l,r-1); } r--; l++; } return true; } public boolean toVlidPalindrome(String s,int l,int r) { while(l<r) { if(s.charAt(l)!=s.charAt(r)) return false; l++; r--; } return true; } } 复制代码时间复杂度：O(n)，其中 n 是字符串的长度。判断整个字符串是否是回文字符串的时间复杂度是 O(n)，遇到不同字符时，判断两个子串是否是回文字符串的时间复杂度也都是 O(n)。
空间复杂度：O(1)。只需要维护有限的常量空间。
作者：Gogo472
链接：https://juejin.cn/post/7022834584005902373