5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

解法一：暴力

用双重循环遍历字符串的所有起始位置与终止位置，然后判断是否是回文子串，是就更新最长长度和回文的起始位置，方便之后分隔字符串成子串。

var longestPalindrome = function(s) {
    //处理特殊情况，长度小于2的就直接返回
    let len=s.length;
    if(len<2){
        return s;
    }
    
    //初始化最长的回文长度、回文起始下标
    let maxLen=1,begin=0;
    // console.log(s.substri/\ng(begin,begin+maxLen));
    //暴力遍历所有情况
    for(let i=0;i maxLen && validP(s,i,j)){
                //更新长度、起始下标
                maxLen=j-i+1;
                begin=i;
            }
        }
        
    }
    return s.substring(begin,begin+maxLen);
};

//创建一个判断回文的函数，左右指针往中心靠拢
function validP(s,left,right){
    while(left<=right){
        if(s[left] != s[right]){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

复杂度分析

• 时间复杂度：\(O(n^3)\)。
• 空间复杂度：\(O(1)\)。

解法二：中心扩散

令一个指针在每遍历一个字符串的下标时，创建一个中心扩散函数进行判断，当左右扩散指针不越界的情况，获取中心点为奇数或偶数（因为中心点可能为1或2个)长度，接着再选择出最长的长度，当指针遍历完后，说明所有的扩散类型都比较完了。

var longestPalindrome = function(s) {
    //处理特殊情况
    let len=s.length;
    if(len<2){
        return s;
    }
    //初始化最长长度和起始位置
    let maxLen=1,begin=0;
    //跟暴力不同，在走向字符串末尾时，一次一次地扩散尝试
    for(let i=0;i< len - 1;i++){
        //考虑奇数与偶数的情况，所以有两种扩散
        let oddLen=expandAroundCenter(s,i,i);
        let evenLen=expandAroundCenter(s,i,i+1);

        //看看奇数还是偶数的情况大，再比较之前的最长长度
        let curMaxLen=Math.max(oddLen,evenLen);
        if(curMaxLen > maxLen){
            maxLen=curMaxLen;
            //根据公式 i-(回文长度-1)/2 知道起始位置，不过这里注意是要向上取整
            begin=Math.ceil(i-(maxLen-1)/2);
        }
    }
    return s.substring(begin,begin+maxLen);
};

//中心扩散
function expandAroundCenter(s,left,right){
    while(left>=0 && right

var longestPalindrome = function(s) {
    let len=s.length;
    if(len<2){
        return s;
    }

    let maxLen=1,begin=0;

    //初始化二维dp，要注意深拷贝和浅拷贝的问题
    let dp=Array.from(new Array(len),()=> new Array(len).fill(false));

    //对角线，即长度为1的子串都是回文串
    for(var i=0;imaxLen){
                maxLen=j-i+1;
                begin=i;
            }
        }
    }
    return s.substring(begin,begin+maxLen);
};