https://leetcode.cn/problems/longest-palindromic-substring/solutions/255195/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

方法一：動態(tài)規(guī)劃

• 思路與算法
• js實現(xiàn)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let len=s.length;
    if(len < 2){
        return s
    }
    let maxLen = 1;
    let begin = 0;
    // dp[i][j]表示s[i...j]是否是回文串
    let dp = new Array(len)
    for(let i=0;i<len;i++){
        dp[i]=new Array(len)
    }
    // 初始化：所有長度為1對子串都是回文串
    for(let i=0;i<len;i++){
        dp[i][i]=true
    }
    console.log(dp)
    // 遞推開始，先枚舉子串長度
    for(let L =2;L<=len;L++){
        // 枚舉左邊界，左邊界的上限設置可以寬松一些
        for(let i=0;i<len;i++){
            // 由L和i可以確定右邊界，即j-i+1=L得
            let j=L+i-1
            // 如果右邊界越界，就可以退出當前循環(huán)
            if(j>=len){
                break;
            }
            if(s[i]!==s[j]){
                dp[i][j]=false
            }else{
                if(j-i<3){
                    // aa或aba格式的
                    dp[i][j]=true
                }else{
                    dp[i][j]=dp[i+1][j-1]
                }
            }

            // 只要dp[i][j]===true成立，就表示子串s[i...j]是回文，此時記錄回文長度和起始位置
            if(dp[i][j]&&j-i+1>maxLen){
                maxLen=j-i+1
                begin = i
                console.log(s.substring(begin,begin+maxLen))
            }
        }
    }
    return s.substring(begin,begin+maxLen)
};

• 復雜度分析
  時間復雜度：O(n^2)，其中 n 是字符串的長度。動態(tài)規(guī)劃的狀態(tài)總數(shù)為 O(n^2)，對于每個狀態(tài)，我們需要轉移的時間為 O(1)。
  空間復雜度：O(n^2)，即存儲動態(tài)規(guī)劃狀態(tài)需要的空間。

方法二：中心擴展算法

• 思路與算法

  
  
  中心擴展算法-思路與算法.png
• js實現(xiàn)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s==null||s.length<1){
        return ''
    }
    let start=0,end=0
    for(let i=0;i<s.length;i++){
        let len1=expandAroundCenter(s,i,i)
        let len2=expandAroundCenter(s,i,i+1)
        let len = Math.max(len1,len2)
        if(len>end-start){
            start=i-Math.floor((len-1)/2)
            end=i+Math.floor(len/2)
            console.log('i----start---end',i,start,end)
        }
    }
    return s.substring(start,end+1)
};
function expandAroundCenter(s,left,right){
    while(left>=0&&right<s.length&&s[left]===s[right]){
        left--
        right++
    }
    return right-left-1
}