leetcode-5-最長迴文子串_前端_奔跑的蝸牛

theme: cyanosis

持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第1天，點選檢視活動詳情

題目地址

給你一個字串 s，找到 s 中最長的迴文子串。

示例 1：

輸入： s = "babad" 輸出： "bab" 解釋： "aba" 同樣是符合題意的答案。

示例 2：

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

提示：

1 <= s.length <= 1000
s 僅由數字和英文字母組成

本文題意很簡單，想要解出來也不難，遍歷所有可能的子串，判斷是否是迴文即可，但是該演算法的時間複雜度為 O(n´³)，時間複雜度太高，會超出時間限制，接下來就讓我為您介紹兩種時間複雜度為 O(n²)的演算法。

解題思路-動態規劃

所謂迴文字串，就是從兩端向中間或者從中間向兩端，每個字元兩兩相等，由此我們可以知道，如果從下標 i 到下標 j 的子串是迴文串，並且 s[i-1]===s[j+1]，則下標 i-1 到下標 j+1 的子串也是迴文串。由以上推導，我們可以定義出動歸的狀態定義和轉移方程。\ 狀態定義：dp[i][j] 表示下標 i 到下標 j 的子串是否是迴文串\ 轉移方程：dp[i][j] = dp[i+1][j-1] && s[i]===s[j]\ 又因為單個字元都是迴文串，所以我們可以基於這個條件初始化所有的 dp[i][i] = true，然後不斷的擴充套件子串長度，直到推匯出所有的子串結果。

程式碼實現

``` var longestPalindrome = function(s) { const len = s.length

if(len===1){
    return s
}

const dp = Array(len)

for(let i = 0;i<len;i++){
    dp[i] = []
    dp[i][i] = true
}

let maxLen = 1
let beginIndex = 0

for(let L = 2;L<=len;L++){
    for(let i = 0;i<=len-L;i++){
        const j = i+L-1

        if(s[i]!==s[j]){
            dp[i][j] = false
        }else{
            if(i===j-1){
                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
            beginIndex = i
        }
    }
}

return s.substring(beginIndex,beginIndex+maxLen)

} ```

解題思路-中心擴充套件

有了動歸解題思路的講解，我們知道可以如果下標 i 到下標 j 的子串是迴文串，則如果 s[i-1]===s[j+1]，下標 i-1 到下標 j+1 的子串也是迴文串。由此可以想到可以列舉所有可能的迴文串中心，通過向兩側擴充套件的方式，找到所有的迴文子串，從而得到最長的迴文子串。

程式碼實現

``` function getMaxBackTextString(s,len,l,r){ if(s[l]!==s[r]){ return 0 } let res = r-l+1 while(l>0 && r<len-1){ l-- r++ if(s[l]===s[r]){ res+=2 }else{ break } }

return res

} var longestPalindrome = function(s) { const len = s.length if(len===1){ return s }

let maxLen = 1
let beginIndex = 0

for(let i = 0;i<len;i++){
    const len1 = getMaxBackTextString(s,len,i,i)
    const len2 = getMaxBackTextString(s,len,i,i+1)

    if(len1>maxLen){
        maxLen = len1
        beginIndex = i-(len1-1)/2
    }
    if(len2>maxLen){
        maxLen = len2
        beginIndex = i-(len2-2)/2
    }
}

return s.substring(beginIndex,beginIndex+maxLen)

} ```

需要注意的是，雖然都是O(n²)的時間複雜度，但是中心擴充套件要比動態規劃更高效，這是因為動態規劃初始化的過程是 O(n)，而且它的推導過程是完整的。而中心擴充套件法遇到無法擴充套件就停止了，而且每次擴充套件是兩個字元長度。\ 還有一部分原因是動態規劃的空間複雜度也是O(n²)，而中心擴充套件的空間複雜度僅為O(1).

至此我們就完成了 leetcode-5-最長迴文子串

如有任何問題或建議，歡迎留言討論！