LeetCode 680 验证回文字符串Ⅱ

[qunzi0214]

题目如下：

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: "aba"
输出: True
示例 2:

输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解题思路一：

对于这个加强版验证回文，首先很容易想到的就是在判别普通回文方法的基础上升级。
当字符串不符合回文格式时，遍历每一个字符串删除后是否符合回文格式。

很显然的问题是，极大提高了时间复杂度，有没有更好的方式呢？

---

解题思路二：

设定左右两个游标，通过逐一比对的方式验证是否满足回文格式，同时如果不满足，左或者右游标可以跳过一次当前字符（即删除当前字符）。

同时考虑一下边界情况，如果left = right - 1 且 删除机会并没有使用，那么意味着前面的比对都通过了，且字符串长度为偶数，那么任意删除当前左右游标的字符，肯定能生成一个满足回文格式的字符串。代码如下

var validPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;
    let chance = 1;
    while(left < right - 1){
        if(s[left] === s[right]){
            left++;
            right--;
        }
        else if(s[left + 1] === s[right] && chance > 0){
            console.log('左边删除', s[left]);
            left++;
            chance--;
        }
        else if(s[right - 1] === s[left] && chance > 0){
            console.log('右边删除', s[right]);
            right--;
            chance--;
        }
        else {
            return false;
        }
    }
    return true;
};

然而事情并没有结束
其中一条没有通过的测试用例是这样的

"aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"

提取出问题发生的核心位置，即：
"cuppucu"这个字符串。

很显然走我的判断函数，那么会删除掉左边的字符c，然后无法形成回文，但是如果删除右边的字符u，是可以生成回文的 (╬￣皿￣)

可以通过再次移动左右游标来排除这种情况，最终代码：

var validPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;
    let chance = 1;
    while(left < right - 1){
        if(s[left] === s[right]){
            left++;
            right--;
        }
        else if(s[left + 1] === s[right] && s[left + 2] === s[right - 1] && chance > 0){
            left++;
            chance--;
        }
        else if(s[right - 1] === s[left] && s[right - 2] === s[left + 1] && chance > 0){
            right--;
            chance--;
        }
        else {
            return false;
        }
    }
    return true;
};

---

附上结果：