如何找到字符串中的最長回文子串?

作者 |channingbreeze

責編 | 胡巍巍

小史是一個應屆生,雖然學的是電子專業,但是自己業餘時間看了很多互聯網與編程方面的書,一心想進BAT互聯網公司。可是努力了很久,別說BAT了,連TMD的橄欖枝都沒有接到。

可是他越挫越勇。這不,今天他又去一家互聯網小巨頭公司面試了。

面試現場

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

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

例如,輸入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

時間空間分析

作者簡介:channingbreeze,國內某互聯網公司全棧開發。

聲明:本文為作者投稿,版權歸對方所有。作者獨立觀點,不代表CSDN 立場。

蘋果手機的微信改版了,

想快速看到CSDN的熱乎文章,

趕快把CSDN公眾號設為星標吧,

打開公眾號,點擊「設為星標」就可以啦!

安卓手機的用戶,

點擊公眾號右上角小人,就可以置頂啦。

征稿啦

CSDN公眾號秉持著「與千萬技術人共成長」理念,不僅以「極客頭條」、「暢言」欄目在第一時間以技術人的獨特視角描述技術人關心的行業焦點事件,更有「技術頭條」專欄,深度解讀行業內的熱門技術與場景應用,讓所有的開發者緊跟技術潮流,保持警醒的技術嗅覺,對行業趨勢、技術有更為全面的認知。

如果你有優質的文章,或是行業熱點事件、技術趨勢的真知灼見,或是深度的應用實踐、場景方案等的新見解,歡迎聯繫CSDN投稿,聯繫方式:微信(guorui_1118,請備註投稿+姓名+公司職位),郵箱([email protected])。

推薦閱讀:

  • 如何快速構建一個 Spring Boot 工程?

  • 國慶通知:地球不爆炸,CSDN 不放假!

  • Python 爬蟲告訴你,國慶這幾個景點千萬別去!

  • 男神不老, 基努里維斯老夥計拍了首部區塊鏈大電影, 還沒上映就燃爆了社交媒體 | 假期薦片

  • 工程師最大黑幕:1.5w代面試,承諾入職頂級公司!

  • 假期快樂!超強面試資源等你Pick,先收藏!

  • 引戰:Java 的開發效率究竟比 C++ 高在哪里?

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