680 验证回文串2.md

680 验证回文字符串2

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

**输入：**s = "aba" **输出：**true

示例 2：

**输入：**s = "abca" **输出：**true **解释：**你可以删除字符 'c' 。

示例 3：

**输入：**s = "abc" **输出：**false

自己写的超时了暴力

function validPalindrome(s: string): boolean {
    if (isH(s)) return true
    let arr = s.split('')
    for (let i = 0; i < s.length; i++) {
        let newArr = arr.slice(0, i).concat(arr.slice(i + 1))
        if (isH(newArr.join(''))) return true
    }
    return false
};

function isH(s: string) {
    return s == s.split('').reverse().join('')
}

正确解法贪心双指针

var isPalindrome = function(s, i, j) {
    while (i < j) {
        if (s[i] !== s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
};

var validPalindrome = function(s) {
    let i = 0, j = s.length - 1;
    while (i < j) {
        if (s[i] !== s[j]) {
            // 删除 s[i] 或者 s[j]
            return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
        }
        i++;
        j--;
    }
    return true; // s 本身就是回文串
};