回文字符串

啥是回文字符串

百科的解释：

题解

这道题起初我力求一个循环不会使用其他函数和递归解出来。但是房子不是一下盖起来的，一口吃不了一个胖子。导致我陷入啦死胡同。因为之前刷题都是一个循环解决问题。这样会让时间复杂度降低，算法跑的更快，但是我老早就知道一个知识点。不管代码的多少与代码的运行时间无关。不是代码写的越多运行速度就流越快。
解题思路：我们先用双指针找出从哪里开始不是回文字符串的，如果找不到那就是一个回文字符串。当找到不是回文字符串的位置，题意中指出可以删除一个字符来让其成为回文字符串。那我们另写一个回文字符串判断函数，将这段不是回文字符串的字符串的左指针或者右指针删除一个字符后判断剩余的是不是回文字符串
图例：
删除一位是回文字符

不是回文字符

遇到不一样的字符。让右指针移动一位判断剩余的字符是不是回文字符串

遇到不一样的字符。让左指针移动一位判断剩余的字符是不是回文字符串

代码

双指针

/**
 * @param {string} s
 * @return {boolean}
 * 回文字符
 * aba abca deeee abc
 * a    b   c   a
 * 0    1   2   3
 * a    c   b   a
 * a    b   c //特殊
 * d    e   e   e   e
 * 0    1   2   3   4
 * e    e   e   e   d
 * a    b   c
 * 0    1   2
 * c    b   a
 *  
 */
var validPalindrome = function(s) {
    if(!s) return false
    let l = 0;
    let r = s.length - 1;
    while(l <= r){
        if(s[l] != s[r]) {
            return isPalindrome(s, l + 1, r) || isPalindrome(s, l, r - 1)
        }
        l++;
        r--;
    }
    return true;
};
function isPalindrome (str, l , r) {
    while(l <= r) {
        if(str[l] != str[r]) return false;
        l++;
        r--;
    }
    return true;
}

双指针+递归

/**
 * @param {string} s
 * @return {boolean}
 * 回文字符
 * aba abca deeee abc
 * a    b   c   a
 * 0    1   2   3
 * a    c   b   a
 * a    b   c //特殊
 * d    e   e   e   e
 * 0    1   2   3   4
 * e    e   e   e   d
 * a    b   c
 * 0    1   2
 * c    b   a
 *  
 */
var validPalindrome = function(s) {
     function valid(l, r, isTrue) {
         while(l < r) {
             if(s[l] != s[r]) {
                 return isTrue ? (valid(l+1, r) || valid(l, r-1)): false;
             }
             l++;
             r--;
         }
        return true;
     }
     return valid( 0, s.length-1, true)
};