最長(zhǎng)回文子串問題是一個(gè)比較經(jīng)典的題目，且字符串的處理問題也比較重要，這里實(shí)現(xiàn)了幾種可行的方法，寫了ac的表示可以通過，有的是可運(yùn)行但是會(huì)超時(shí)或者是超過內(nèi)存限制。

一：優(yōu)化的暴力和暴力解

1.1 算是優(yōu)化后的暴力解【AC】

其實(shí)我感覺這個(gè)解法和最長(zhǎng)公共子串的復(fù)雜度應(yīng)該是差不多吧，反正時(shí)間復(fù)雜度也很高就是了，險(xiǎn)險(xiǎn)的AC。。

拿到這個(gè)題的時(shí)候，我腦子里想的是，可以試試我的左右指針了，然后就出現(xiàn)了下面的代碼，雖然wa了好幾次，但是最后修修補(bǔ)補(bǔ)邊界條件最終還是過了，雖然耗時(shí)比較久。。。不過在判斷的條件上花了些心思，這樣的話可以避免存儲(chǔ)的問題，也避免了一些無效的字串，算是對(duì)爆破的時(shí)間復(fù)雜度優(yōu)化了一點(diǎn)吧。大致思路如下：

第一層循環(huán)固定第一個(gè)值，然后第二個(gè)指針從后往前走，先找到和第一個(gè)指針的值相等的下標(biāo)，并且記錄這個(gè)下標(biāo)R，從這個(gè)下標(biāo)開始比較，判斷是否存在回文串，如果不存在，那么就從下標(biāo)R-1開始繼續(xù)上述的過程。

整個(gè)題目出錯(cuò)的點(diǎn)，都寫在注釋里了，邊界條件總是會(huì)搞不準(zhǔn)，而且flag的設(shè)置一開始定位不準(zhǔn)確，都是一開始的思路不是很清楚導(dǎo)致的，比較關(guān)鍵的一個(gè)錯(cuò)誤是，if條件判斷不準(zhǔn)確，導(dǎo)致下標(biāo)發(fā)生了錯(cuò)誤，再就是在一次字串判斷失敗以后，應(yīng)該讓左指針恢復(fù)原來的i，否則會(huì)導(dǎo)致漏掉一些字串。

string

1.2 暴力解

下面的解決方法是最直接的暴力，會(huì)超出內(nèi)存限制，應(yīng)該是存reverse的時(shí)候超出了內(nèi)存限制；【但我比較奇怪的是，不是有方法是最長(zhǎng)公共子串嗎，這不是要把每一個(gè)字符串都reverse嗎，那這種方法理論上也會(huì)超出內(nèi)存？？】

我嘗試了一個(gè)一個(gè)的判斷，這樣的話時(shí)間復(fù)雜度也會(huì)上來，最后也超出了時(shí)間限制，所以單純的爆破在這里應(yīng)該是不可以AC的。。

// 第一種暴力

二、最長(zhǎng)公共子序列

對(duì)字符串逆序，然后找到最長(zhǎng)公共子串，還需要判斷這個(gè)公共子串是否是回文數(shù)。比較悲傷的是，這個(gè)還是會(huì)超時(shí)。

class

三、中心擴(kuò)展法【AC】

這個(gè)方法其實(shí)比較好理解，就是回文串一定是一個(gè)對(duì)稱的存在，所以可以從對(duì)稱中心出發(fā)，去尋找以當(dāng)前中心出發(fā)的回文串的大小，然后挨個(gè)比較就可以了。

我這個(gè)出錯(cuò)的點(diǎn)在于，已知字符串的長(zhǎng)度和中心點(diǎn)的下標(biāo)，如何求出來字符串的起始位置？但其實(shí)也可以直接讓函數(shù)返回一個(gè)字符串就沒有這種煩惱了，第二種就是這樣寫的，時(shí)間上還快了很多。

class

第二種返回字符串的方法

class

四、動(dòng)態(tài)規(guī)劃

搓手手，要?jiǎng)討B(tài)規(guī)劃了，嚶嚶嚶。對(duì)這個(gè)算法有著一些些的畏懼心理，數(shù)據(jù)結(jié)構(gòu)小老頭講的太無趣，并且成功錯(cuò)過了高神的動(dòng)歸課，當(dāng)然這都不是理由，重點(diǎn)是。。。懶于思考的我，活該菜狗。【好吧，其實(shí)寫這個(gè)的時(shí)候，感覺還是沒有理解透徹什么是動(dòng)態(tài)規(guī)劃，，等我好好學(xué)習(xí)一下左神的視頻以后，理解的更深刻了再來更新好了！】

class

總結(jié)

以上是生活随笔為你收集整理的怎么判断一个字符串的最长回文子串是否在头尾_LeetCode5：最长回文子串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。