本次題目描述：

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

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

示例 1:

// 輸入: 
"babad"



// 輸出: 
"bab"



// 注意: 
"aba" 也是一個(gè)有效答案。

示例 2:

// 輸入: 
"cbbd"



// 輸出: 
"bb"

解題思路

解法1 - 中心拓展法

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

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

意思就是有 i + i - 1個(gè)拓展中心。

則 i 為奇數(shù)位，

i + 1為偶數(shù)位。

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

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

空間復(fù)雜度是O(1)。

解法2 - 馬拉車算法

第一次接觸這個(gè)算法，但是想出這個(gè)算法的人，確實(shí)牛逼。

馬拉車算法將時(shí)間復(fù)雜度提升到了線性。

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

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

保證當(dāng)前字符串一定為奇數(shù)。

然后左右擴(kuò)展。

利用一個(gè)長度為原字符串長度的數(shù)組arr來保存中心擴(kuò)展的大個(gè)數(shù)。

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

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

這時(shí)候就可以用中心擴(kuò)展法去求。

我們用j表示第i個(gè)字符與C對應(yīng)的下標(biāo)。

但有以下三種情況會導(dǎo)致arr[j]不正確

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

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

網(wǎng)站欄目：Python和Java解題：最長回文子串-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://www.aaarwkj.com/article2/jedic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供關(guān)鍵詞優(yōu)化、全網(wǎng)營銷推廣、軟件開發(fā)、品牌網(wǎng)站建設(shè)、網(wǎng)站營銷、靜態(tài)網(wǎng)站

廣告

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