剑指 Offer II 019. 最多删除一个字符得到回文(Javascript)

本文主要是介绍剑指 Offer II 019. 最多删除一个字符得到回文(Javascript)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、题目地址

https://leetcode-cn.com/problems/RQku0D/

二、具体代码

/**
 * @param {string} s
 * @return {boolean}
 */
// 双指针解法
// 时间复杂度: 最好时为O(n), 最差时为O(n^2),n为s的长度
// 空间复杂度: o(1)
var validPalindrome = function(s) {
    let left = 0;
    let right = s.length - 1;
    while(left < right) {
        if(s[left] !== s[right]) {
        /* 
            如果不相等,则分两种情况:删除左边的元素，或者右边的元素，
            再判断各自是否回文，满足一种即可。
         */
            return isPalinedrome(s, left+1, right) || isPalinedrome(s, left, right-1);
        }
        left++;
        right--;
    }
    return true;
};
// 判断字符串 s 的 [left, right] 是否回文
function isPalinedrome(s, left, right) {
    while(left < right) {
        if(s[left++] !== s[right--]) {
            return false;
        }
    }
    return true;
}

三、具体思想

1、解题思路
此题和判断一个字符串是不是回文字符串只有一个差别：

是否有一次删除一个字符的机会。
所以，这道题我们依旧使用双指针法。

2、算法流程

设定左右指针，将二者分别指向字符串的两边。
依次比较左右指针对应的字符是否相等。
如果相等，继续比较剩下的字符。
如果不相等，则分两种情况，只要有一种情况是回文字符串即可：
删除左边的 left 指针指向的元素，判断 s[left+1, right] 是否回文。
删除右边的 right 指针指向的元素，判断 s[left, right-1] 是否回文。

这篇关于剑指 Offer II 019. 最多删除一个字符得到回文(Javascript)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！