本次題目描述：

創新互聯專注于平輿企業網站建設,成都響應式網站建設公司,商城開發。平輿網站建設公司,為平輿等地區提供建站服務。全流程按需求定制制作，專業設計，全程項目跟蹤，創新互聯專業和態度為您提供的服務

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的大長度為 1000。

示例 1:

// 輸入: 
"babad"



// 輸出: 
"bab"



// 注意: 
"aba" 也是一個有效答案。

示例 2:

// 輸入: 
"cbbd"



// 輸出: 
"bb"

解題思路

解法1 - 中心拓展法

由于回文字符串的對稱性，所以每次可以選擇一個數字作為中心，進行左右拓展來判斷是否是回文串。

由于字符串有可能為奇數，有可能為偶數，所以需要從 1 or 2個字符之間開始拓展。

意思就是有 i + i - 1個拓展中心。

則 i 為奇數位，

i + 1為偶數位。

以此為理論依據每次循環往兩邊拓展即可。

此解法時間復雜度是O(n^2)。

空間復雜度是O(1)。

解法2 - 馬拉車算法

第一次接觸這個算法，但是想出這個算法的人，確實牛逼。

馬拉車算法將時間復雜度提升到了線性。

此算法最初遍歷字符，在每個字符兩邊都插入一個特殊符號，為避免越界，首尾加上特殊標簽，例如：

aabbcbbaa -> ^#a#a#b#b#c#b#b#a#a#$

保證當前字符串一定為奇數。

然后左右擴展。

利用一個長度為原字符串長度的數組arr來保存中心擴展的大個數。

(arr每個元素的下標 - arr[i]) / 2 就是原字符串的字符的下標。

我們設C為字符串中心，R為字符串右邊的長度，則有R = C + arr[i]。

這時候就可以用中心擴展法去求。

我們用j表示第i個字符與C對應的下標。

但有以下三種情況會導致arr[j]不正確

1. 長度超出了R
2. arr[j]到了原字符串的左邊界
3. 當i就是為R時

所以遇到以上三種情況，我們需要利用中心拓展法去做邊界處理。

網站欄目：Python和Java解題：最長回文子串-創新互聯
網頁鏈接：http://vcdvsql.cn/article2/jedic.html

成都網站建設公司_創新互聯，為您提供關鍵詞優化、全網營銷推廣、軟件開發、品牌網站建設、網站營銷、靜態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯