LeetCode 680 Valid Palindrome II javascript solution

Determine whether a string can be a palindrome with at most one character removed, i.e. read from the beginning and read from the end. link:https://leetcode.com/problems/valid-palindrome-ii/description/

Attemp1: Easy to reverse strings with str.split(” “).reverse().join(” “). First determine whether the string itself is palindrome, and then perform a loop on the string, one string by string removal comparison, can become a palindrome. I’m not going to worry about performance because I have an easy title. Time Exceeded, SAD…

Attemp2: Remove the number of characters using the attempt variable outside function, and return false once the number exceeds 1. The loop starts at the beginning of the character and ends before half way through it. Check if arr[0] (head) and arr[arr.length-1 (tail) are the same. If so, remove the head and end until the length of the string is less than 2. And of course, tolerate++, if tolerate > 1, directly out, not greater than 1, creates two strings, arr_left, and removes arr[0] from the resulting ARR, and arr_right, The arr (arr. Length – 1) delete the generated arr, recursive calls, returns validPalindrome (arr_left) | | validPalindrome (arr_right). 1. Arr_left = arr; 2. Arr_left. Splice (0, 1), shallow copy, any operation to arr_left will directly affect the ARR, arr_right will be affected, there is a trick: Arr_left = JSON. Parse (JSON. Stringify (arr)). So it doesn’t point to the same address. 2. It is more convenient to convert string to array. if(! Array. IsArray (STR)) {STR = STR. The split (‘ ‘)} 3, leetCode tolerate variable defined in the function outside, at the time of actual submit code execution, will fail, You have to put tolerate in the function. if(typeof tolerate === ‘undefined’){ tolerate = 0; } post code:

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s, tolerate) {
    if(typeof(tolerate) === 'undefined'){
        tolerate = 0;
    }
    if(! Array.isArray(s)){ s = s.split(' ');
    }
    while(s.length > 1){
        if(s[0] == s[s.length - 1]){
            s.splice(0, 1);
            s.splice(s.length - 1, 1);
        }else{
            tolerate++;
            if(tolerate > 1)
                return false;
            let sLeft = JSON.parse(JSON.stringify(s));
            sLeft.splice(0, 1);
            let sRight = JSON.parse(JSON.stringify(s));
            sRight.splice(sRight.length - 1);
            returnvalidPalindrome(sLeft, tolerate) || validPalindrome(sRight, tolerate); }}return true;
};
Copy the code