【面試現場】如何找到字符串中的最長回文子串?

點擊上方「程序人生」,選擇「置頂公眾號」

第一時間關注程序猿(媛)身邊的故事

【面試現場】

小史:只要先對比第一個字符和倒數第一個字符,再對比第二個字符和倒數第二個字符,以此類推。如果都相等,那就是回文串了。

題目:給你一個字符串,找出里面最長的回文子串。

例如

輸入abcdcef,那麼輸出應該是cdc

輸入adaelele,輸出應該是elele

半分鐘過去了。

小史:可以遍歷整個字符串,把每個字符和字符間的空隙當作回文的中心,然後向兩邊擴展來找到最長回文串。

小史這次搶著分析時間和空間複雜度。

一分鐘過去了。

【請教大神】

小史回到學校,把面試情況和呂老師說了一下。

呂老師:比如cabadabae用中心擴展的算法,我已經知道了第三位為中心的aba和第5位為中心的abadaba是回文,那麼在判斷第7位為中心的回文串的時候,有什麼已知信息嗎?

小史:已知第5位為中心的abadaba是回文,由回文的特性,就能夠知道2-4位和6-8位對稱,而又知道第3位為中心的aba是回文,所以2-4位是回文。這樣的話,6-8位肯定是回文。

小史拿著筆在紙上畫了半天,突然大叫一聲。

小史:由於之前的計算已經知道了第5位為中心的abadaba是回文,而第4位為中心的a的回文長度是1,所以第6位為中心的回文長度只能是1,不用再去擴展判斷了。

小史:以第7位為中心的回文串的計算,由之前分析已經知道最小長度是3了,但是還是需要進行擴展,因為第9位是什麼根據之前的信息無法得知,需要擴展進行探索。

小史:而以第6位為中心的回文串的計算,並不需要進行探索了,因為根據之前第5位為回文中心串的信息和第4位為回文中心串的信息已經可以推斷第6位為回文中心串的長度只能為1。

小史:當然可以。

1、首先,我們要記錄下目前已知的回文串能夠覆蓋到的最右邊的地方,就像案例中的第8位

2、同時,覆蓋到最右邊的回文串所對應的回文中心也要記錄,就像案例中的第5位

3、以每一位為中心的回文串的長度也要記錄,後面進行推斷的時候能用到,就像案例中用到的以第3位為中心的回文和第4位為中心的回文

4、對於新的中心,我們判斷它是否在右邊界內,若在,就計算它相對右邊界回文中心的對稱位置,從而得到一些信息,同時,如果該中心需要進行擴展,則繼續擴展就行。

【編碼做到】

小史:回文的中心有可能是兩個字符中間,這種情況沒有考慮到啊。

小史:

1、先對字符串進行預處理,兩個字符之間加上特殊符號#

2、然後遍歷整個字符串,用一個數組來記錄以該字符為中心的回文長度,為了方便計算右邊界,我在數組中記錄長度的一半(向下取整)

3、每一次遍歷的時候,如果該字符在已知回文串最右邊界的覆蓋下,那麼就計算其相對最右邊界回文串中心對稱的位置,得出已知回文串的長度

4、判斷該長度和右邊界,如果達到了右邊界,那麼需要進行中心擴展探索。當然,如果第3步該字符沒有在最右邊界的「羽翼」下,則直接進行中心擴展探索。進行中心擴展探索的時候,同時又更新右邊界

5、最後得到最長回文之後,去掉其中的特殊符號即可

理解了算法之後,小史的代碼寫起來也是非常快,不一會兒就寫好了:

PlalindromeString.java

/***@authorxiaoshion2018/9/24.*HappyMid-AutumnFestival*/publicclassPlalindromeString{//判斷一個字符串是否回文,算法中用不到了@DeprecatedprivatebooleanisPlalindrome(Strings){intlen=s.length();for(inti=0;i<len/2;i++){if(s.charAt(i)!=s.charAt(len-1-i)){returnfalse;}}returntrue;}//預處理字符串,在兩個字符之間加上#privateStringpreHandleString(Strings){StringBuffersb=newStringBuffer();intlen=s.length();sb.append('#');for(inti=0;i<len;i++){sb.append(s.charAt(i));sb.append('#');}returnsb.toString();}//尋找最長回文字串publicStringfindLongestPlalindromeString(Strings){//先預處理字符串Stringstr=preHandleString(s);//處理後的字串長度intlen=str.length();//右邊界intrightSide=0;//右邊界對應的回文串中心intrightSideCenter=0;//保存以每個字符為中心的回文長度一半(向下取整)int[]halfLenArr=newint[len];//記錄回文中心intcenter=0;//記錄最長回文長度intlongestHalf=0;for(inti=0;i<len;i++){//是否需要中心擴展booleanneedCalc=true;//如果在右邊界的覆蓋之內if(rightSide>i){//計算相對rightSideCenter的對稱位置intleftCenter=2*rightSideCenter-i;//根據回文性質得到的結論halfLenArr[i]=halfLenArr[leftCenter];//如果超過了右邊界,進行調整if(i+halfLenArr[i]>rightSide){halfLenArr[i]=rightSide-i;}//如果根據已知條件計算得出的最長回文小於右邊界,則不需要擴展了if(i+halfLenArr[leftCenter]<rightSide){//直接推出結論needCalc=false;}}//中心擴展if(needCalc){while(i-1-halfLenArr[i]>=0&&i+1+halfLenArr[i]<len){if(str.charAt(i+1+halfLenArr[i])==str.charAt(i-1-halfLenArr[i])){halfLenArr[i]++;}else{break;}}//更新右邊界及中心rightSide=i+halfLenArr[i];rightSideCenter=i;//記錄最長回文串if(halfLenArr[i]>longestHalf){center=i;longestHalf=halfLenArr[i];}}}//去掉之前添加的#StringBuffersb=newStringBuffer();for(inti=center-longestHalf+1;i<=center+longestHalf;i+=2){sb.append(str.charAt(i));}returnsb.toString();}}

Main.java

/***@authorlixinon2018/9/24.*/publicclassMain{publicstaticvoidmain(String[]args){PlalindromeStringps=newPlalindromeString();String[]testStrArr=newString[]{"abcdcef","adaelele","cabadabae","aaaabcdefgfedcbaa","aaba","aaaaaaaaa"};for(Stringstr:testStrArr){System.out.println(String.format("原字串:%s",str));System.out.println(String.format("最長回文串:%s",ps.findLongestPlalindromeString(str)));System.out.println();}}}

運行結果:

原字串:abcdcef最長回文串:cdc原字串:adaelele最長回文串:elele原字串:cabadabae最長回文串:abadaba原字串:aaaabcdefgfedcbaa最長回文串:aabcdefgfedcbaa原字串:aaba最長回文串:aba原字串:aaaaaaaaa最長回文串:aaaaaaaaa

【時間空間分析】

– The End –

「若你有原創文章想與大家分享,歡迎投稿。」

加編輯微信ID,備註#投稿#:

程序 丨 druidlost

小七 丨 duoshangshuang

2018 AI開發者大會

拒絕空談,技術爭鳴

2018 AI開發者大會重磅嘉賓及深度議題已火熱出爐,掃碼搶「鮮」看。國慶特惠,票價立享 5 折優惠!

往期精彩內容

print_r('點個讚吧');var_dump('點個讚吧');NSLog(@"點個讚吧!")System.out.println("點個讚吧!");console.log("點個讚吧!");print("點個讚吧!");printf("點個讚吧!\n");cout << "點個讚吧!" << endl;Console.WriteLine("點個讚吧!");fmt.Println("點個讚吧!")Response.Write("點個讚吧");alert(’點個讚吧’)

[do_widget id=yuzo_widget-4] [do_widget id=yuzo_widget-9] 職場