最长回文子串-动态规划算法

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

方法一：动态规划

• 思路与算法
• js实现

/**
 * @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
            // 如果右边界越界，就可以退出当前循环
            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 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
  空间复杂度：O(n^2)，即存储动态规划状态需要的空间。

方法二：中心扩展算法

• 思路与算法

  
  
  中心扩展算法-思路与算法.png
• js实现

/**
 * @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
}