验证回文字符串 Ⅱ

验证回文字符串 Ⅱ

力扣上第680题

核心思想

使用双指针，即使用前后两个指针，同时对前指针和后指针的值做对比，要是相同，那么前指针向后移动，后指针向前移动
但这道题说可以删除一个字符, 那么当我们遇到不相等的值的时候，只要前指针向后移动，或者后指针向前移动，然后剩下的做对比即可

• 终止条件为： 前指针 比 后指针要大，或者说是前指针后于后指针

解释

上图，我们只要判断左指针和右指针的值是否相等，直到终止条件，要是全部都相同，那么就是回文了

但这题说可以删除一个字母，那么等字符不相等的时候，左指针向后移动或者右指针向前移动，将剩下的再做一次回文即可，看下图

代码

// "ebcbb ececabbacec bbcbe"
// "ebcbb cecabbacece bbcbe"
var validPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;
    let flag = false; // 标志位 表示要是遇到一个前指针与后指针不相同的值, 退出循环。
    while(left < right) {
        const leftTemp = s[left];
        const rightTemp = s[right];
        if(leftTemp == rightTemp) {
            left++;
            right--;
        } else {
            flag = true;
            break;
        }
    } 
    if(flag >= 1) {
        const tempString = s.slice(left + 1, right + 1);
        return validChilren(left+1, right, s) || validChilren(left, right - 1, s);
    }
    return true;
};

function validChilren(left, right, s) {
    while(left < right) {
        const leftTemp = s[left];
        const rightTemp = s[right];
        if(leftTemp == rightTemp) {
            left++;
            right--;
        } else {
            return false;
        }
    }
    return true;
}