验证回文字符串 Ⅱ

[CodeRookie262]

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

示例 1:

输入: "aba"
输出: True

示例 2:

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

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

来源：力扣（LeetCode）

[CodeRookie262]

var validPalindrome = function (s) {
    let i = 0,
        l = s.length - 1;
    // 双指针遍历字符串
    while (i < l) {
        // 如果遇到差异则分别将左右指针+1，-1，判断接下来的字符串是否是回文
        if (s[i] !== s[l]) {
            return isPalindrome(s, i + 1, l) || isPalindrome(s, i, l - 1)
        }
        i++;
        l--;
    }

    return true;
};


// 判断是否是回文字符串
const isPalindrome = (s, start, end) => {
    while (start < end) {
        if (s[start] !== s[end]) return false;
        start++;
        end--;
    }
    return true;
}

[yuki-mirai]

实现不错，这种题普遍的思想是从两侧开始逐渐往中间收窄区间，难出其右。独立出一个方法专门用于判断回文，减少了代码冗余。利用高低位指针作为循环的继续条件，还减少了中位变量。👍

这道题很巧妙，相较于单纯的判断是否回文，加上了“可以删除一个元素”的条件后，情况变得复杂。我一开始在遇到不相等的元素时只计算：

1. 低位向前看一位是否与高位相等
2. 高位向前看一位是否与低位相等

没将二者结合起来，结果遇到：

aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga

这个流氓直接给我返回了false(ˉ▽ˉ；)...

var validPalindrome = function (s) {
    if (!s) return false;

    for (let lstIdx = s.length - 1, i = 0; i < lstIdx; i++, lstIdx--) {

        // 遇到不等的情况，从不等位开始，计算剩余字串
        if (s.charAt(i) !== s.charAt(lstIdx)) {
            // 可以删除一个元素，那么分别计算：
            // 1. 低位向前看一位（+1），是否与高位相等
            // 2. 高位向前看一位（-1），是否与低位相等
            // 只要有一个结果计算是回文，那么就是回文。
            // 因为存在类似：aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga
            // 这样的“流氓”，
            // cupuu
            // uupucu
            // 低位向前一位相等，容易让我们误以为是回文，但是下个元素直接打脸，而高位向前结果是回文，
            // 因此高低位向前均要同时考虑。
            let r1 = true, r2 = true;
            // 低位元素略过一位，计算剩余是否回文
            for (let l1 = i + 1, h1 = lstIdx; l1 < h1; l1++, h1--) {
                // 已经略过一个元素了，再不相等结果为false并跳出
                if (s.charAt(l1) !== s.charAt(h1)) r1 = false; break;
            }

            // 高位元素略过一位，计算剩余是否回文
            for (let l2 = i, h2 = lstIdx - 1; l2 < h2; l2++, h2--) {
                // 已经略过一个元素了，再不相等结果为false并跳出
                if (s.charAt(l2) !== s.charAt(h2)) r2 = false; break;
            }

            return r1 || r2;
        }
    }

    return true; // 不删除元素，本身是回文
};

[CodeRookie262]

嗯嗯，这道题难点在非回文字符串如何进行取舍处理 @Mirai39