本次題目描述：

創(chuàng)新互聯(lián)專注于平輿企業(yè)網站建設,成都響應式網站建設公司,商城開發(fā)。平輿網站建設公司,為平輿等地區(qū)提供建站服務。全流程按需求定制制作，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務

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

示例 1:

// 輸入: 
"babad"



// 輸出: 
"bab"



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

示例 2:

// 輸入: 
"cbbd"



// 輸出: 
"bb"

解題思路

解法1 - 中心拓展法

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

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

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

則 i 為奇數位，

i + 1為偶數位。

以此為理論依據每次循環(huán)往兩邊拓展即可。

此解法時間復雜度是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解題：最長回文子串-創(chuàng)新互聯(lián)
標題網址：http://weahome.cn/article/jedic.html