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<len-1;i++){
        for(let j=i+1;j<len;j++){
            //如果长度比之前的长，并且判断出是回文
            if(j-i+1 > 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<s.length && s[left]===s[right]){
        //符合情况的就扩散
        left--,right++;
    }
    //由于先判断再循环的while，存在扩散超出回文长度的边界的情况，刚好变得不再是回文情况，所以是（right-left+1-2），而不是right-left+1
    console.log(right,left)
    return right-left-1;
}

复杂度分析

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

解法三：动态规划

可以知道如果判断字符串是回文子串，那么抛开前后两端，就由中间决定了以下图举例：

我要保证j>i，即右指针要大于左指针，而下面红线指示的例子就是表示抛开前后两端看中间又怎么样，以此循环。

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;i<len;i++){
        dp[i][i]=true;
    }
    //从列开始数,不用从0开始，因为第0列本身没比较的价值
    for(var j=1;j<len;j++){
        //只用看右上角的比对情况，所以是i<j，i代表从左端往中间的值，j代表从右端往中间的值
        for(var i=0;i<j;i++){
            //如果左右两端不匹配就说明不符合
            if(s[i]!=s[j]){
                dp[i][j]=false;
            //如果两端匹配了
            }else{
                //此时的子串太短或者是没有的情况，也就没必要比下去了
                if(j-i<3){
                    dp[i][j]=true;
                //如果还太长，就继续比下去，左右两端指针继续往中间移动
                }else{
                    dp[i][j]=dp[i+1][j-1];
                }
            }
            //最后就不断更新获取最长的长度
            if(dp[i][j] && j-i+1>maxLen){
                maxLen=j-i+1;
                begin=i;
            }
        }
    }
    return s.substring(begin,begin+maxLen);
};

复杂度分析

• 时间复杂度：\(O(n^2)\)，其中 \(n\) 是字符串的长度。动态规划的状态总数为 \(O(n^2)\)，对于每个状态，我们需要转移的时间为 \(O(1)\)。
• 空间复杂度：\(O(n^2)\)，即存储动态规划状态需要的空间。

解法四：Manacher算法（马拉车算法）

太难了，后面解决。