【面试现场】如何找到字符串中的最长回文子串？

傷城~ 2022-04-03 07:22 211阅读 0赞

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。

![2018122023073542][]

今天他又去一家互联网小巨头公司面试了。

![2018122023073563][]

**【面试现场】**

![2018122023073584][]

![20181220230735190][]

![20181220230735214][]

![20181220230735229][]

![20181220230735316][]

![20181220230735333][]

![20181220230735356][]

小史：只要先对比第一个字符和倒数第一个字符，再对比第二个字符和倒数第二个字符，以此类推。如果都相等，那就是回文串了。

![20181220230735376][]

题目：给你一个字符串，找出里面最长的回文子串。

例如

输入abcdcef，那么输出应该是cdc

输入adaelele，输出应该是elele

![20181220230735391][]

![20181220230735408][]

![20181220230735422][]

![20181220230735438][]

![20181220230735453][]

半分钟过去了。

![20181220230735565][]

![20181220230735577][]

![20181220230735596][]

小史：可以遍历整个字符串，把每个字符和字符间的空隙当作回文的中心，然后向两边扩展来找到最长回文串。

小史这次抢着分析时间和空间复杂度。

![20181220230735613][]

![20181220230735732][]

![20181220230735815][]

一分钟过去了。

![20181220230735920][]

![20181220230735936][]

![20181220230735952][]

![20181220230735968][]

**【请教大神】**

小史回到学校，把面试情况和吕老师说了一下。

![20181220230735986][]

![2018122023073682][]

吕老师：比如cabadabae用中心扩展的算法，我已经知道了第三位为中心的aba和第5位为中心的abadaba是回文，那么在判断第7位为中心的回文串的时候，有什么已知信息吗？

![20181220230736178][]

![20181220230736192][]

小史：已知第5位为中心的abadaba是回文，由回文的特性，就能够知道2-4位和6-8位对称，而又知道第3位为中心的aba是回文，所以2-4位是回文。这样的话，6-8位肯定是回文。

![20181220230736227][]

![20181220230736243][]

![20181220230736316][]

![20181220230736334][]

![20181220230736423][]

小史拿着笔在纸上画了半天，突然大叫一声。

![20181220230736439][]

小史：由于之前的计算已经知道了第5位为中心的abadaba是回文，而第4位为中心的a的回文长度是1，所以第6位为中心的回文长度只能是1，不用再去扩展判断了。

![20181220230736454][]

![20181220230736471][]

![20181220230736489][]

![20181220230736511][]

![20181220230736537][]

小史：以第7位为中心的回文串的计算，由之前分析已经知道最小长度是3了，但是还是需要进行扩展，因为第9位是什么根据之前的信息无法得知，需要扩展进行探索。

![20181220230736550][]

![20181220230736636][]

小史：而以第6位为中心的回文串的计算，并不需要进行探索了，因为根据之前第5位为回文中心串的信息和第4位为回文中心串的信息已经可以推断第6位为回文中心串的长度只能为1。

![20181220230736656][]

![20181220230736742][]

![20181220230736763][]

![20181220230736844][]

![20181220230736860][]

![20181220230736945][]

![20181220230736965][]

![20181220230736983][]

![201812202307370][]

![2018122023073716][]

小史：当然可以。

1、首先，我们要记录下目前已知的回文串能够覆盖到的最右边的地方，就像案例中的第8位

2、同时，覆盖到最右边的回文串所对应的回文中心也要记录，就像案例中的第5位

3、以每一位为中心的回文串的长度也要记录，后面进行推断的时候能用到，就像案例中用到的以第3位为中心的回文和第4位为中心的回文

4、对于新的中心，我们判断它是否在右边界内，若在，就计算它相对右边界回文中心的对称位置，从而得到一些信息，同时，如果该中心需要进行扩展，则继续扩展就行。

**【编码实现】**

![2018122023073732][]

![20181220230737123][]

小史：回文的中心有可能是两个字符中间，这种情况没有考虑到啊。

![20181220230737137][]

![20181220230737245][]

![20181220230737261][]

![20181220230737277][]

![20181220230737293][]

小史：

1、先对字符串进行预处理，两个字符之间加上特殊符号\#

2、然后遍历整个字符串，用一个数组来记录以该字符为中心的回文长度，为了方便计算右边界，我在数组中记录长度的一半（向下取整）

3、每一次遍历的时候，如果该字符在已知回文串最右边界的覆盖下，那么就计算其相对最右边界回文串中心对称的位置，得出已知回文串的长度

4、判断该长度和右边界，如果达到了右边界，那么需要进行中心扩展探索。当然，如果第3步该字符没有在最右边界的“羽翼”下，则直接进行中心扩展探索。进行中心扩展探索的时候，同时又更新右边界

5、最后得到最长回文之后，去掉其中的特殊符号即可

![20181220230737311][]

![20181220230737333][]

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

PlalindromeString.java

/\*\*

\*@authorxiaoshi on 2018/9/24.

\* Happy Mid-Autumn Festival

\*/

publicclassPlalindromeString\{

// 判断一个字符串是否回文，算法中用不到了

@Deprecated

privatebooleanisPlalindrome(String s)\{

intlen = s.length();

for(inti =0; i < len /2; i++) \{

if(s.charAt(i) != s.charAt(len -1- i)) \{

returnfalse;

returntrue;

// 预处理字符串，在两个字符之间加上\#

privateStringpreHandleString(String s)\{

StringBuffer sb =newStringBuffer();

intlen = s.length();

sb.append('\#');

for(inti =0; i < len; i++) \{

sb.append(s.charAt(i));

sb.append('\#');

returnsb.toString();

// 寻找最长回文字串

publicStringfindLongestPlalindromeString(String s)\{

// 先预处理字符串

String str = preHandleString(s);

// 处理后的字串长度

intlen = str.length();

// 右边界

intrightSide =0;

// 右边界对应的回文串中心

intrightSideCenter =0;

// 保存以每个字符为中心的回文长度一半（向下取整）

int\[\] halfLenArr =newint\[len\];

// 记录回文中心

intcenter =0;

// 记录最长回文长度

intlongestHalf =

for(int i = 0; i < len; i++) \{

// 是否需要中心扩展boolean needCalc = true;

// 如果在右边界的覆盖之内if(rightSide > i) \{

// 计算相对rightSideCenter的对称位置int leftCenter = 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\];

// 去掉之前添加的\#

StringBuffer sb =

newStringBuffer();

for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) \{

sb.append(str.charAt(i));

returnsb.toString();

Main.java

/\*\*

\* @author lixin on 2018/9/24.

\*/

publicclassMain\{

publicstaticvoidmain(String\[\] args)\{

PlalindromeString ps =newPlalindromeString();

String\[\] testStrArr =newString\[\] \{

"abcdcef",

"adaelele",

"cabadabae",

"aaaabcdefgfedcbaa",

"aaba",

"aaaaaaaaa"

\};

for(String str : 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

![20181220230737352][]

**【时间空间分析】**

![20181220230737370][]

![20181220230737392][]

![20181220230737409][]

![20181220230737430][]

![20181220230737448][]

![20181220230737465][]

![20181220230737497][]

![20181220230737512][]

![20181220230737530][]

![20181220230737551][]

***扩展阅读***

[【面试现场】如何实现可以获取最小值的栈？][Link 1]

[【面试现场】如何在10亿数中找出前1000大的数][10_1000]

[【面试现场】为什么要分稳定排序和非稳定排序？][Link 2]

来源：互联网侦察

> ### 微信公众号：javafirst ###
> 
> ### 扫码关注免费获取更多资源  ###
> 
> ![70][]

[2018122023073542]: /images/20220403/291b448db0284bdd9b2ee053b6bd47a6.png
[2018122023073563]: /images/20220403/a8fb65c0f70d4bd9bb4a07a23a3c36c0.png
[2018122023073584]: /images/20220403/70040d1ef0704368b76ee390a826eb18.png
[20181220230735190]: /images/20220403/5ea28716271e4cbf8ef61cc4d498a4ea.png
[20181220230735214]: /images/20220403/562cfa1105134b22a1cc425bd2f34767.png
[20181220230735229]: /images/20220403/75248d5cfb294e7892e79a15f55a61df.png
[20181220230735316]: /images/20220403/553ea34563aa4f20854541bac6104d8e.png
[20181220230735333]: /images/20220403/d8fed0c4201540dcbc053556b89f7c08.png
[20181220230735356]: /images/20220403/a38431eed62b46cda972a2ff4605740f.png
[20181220230735376]: /images/20220403/5052cc7db0524cee90319f2d6e16036a.png
[20181220230735391]: /images/20220403/6ea0227feb7d4b8e8c6cf0e3f7111c82.png
[20181220230735408]: /images/20220403/66ad2f08e54a4ff99ac01f905490e41d.png
[20181220230735422]: /images/20220403/291b448db0284bdd9b2ee053b6bd47a6.png2
[20181220230735438]: /images/20220403/e8ff6ed6b69a483c88fbb1d473ee7d59.png
[20181220230735453]: /images/20220403/0406ef6be51c4ba6bd95e265d02c2f29.png
[20181220230735565]: /images/20220403/e4d97b669b9e4a3ba447be456a2d07ee.png
[20181220230735577]: /images/20220403/4b7bf3a0eda14be4b417b0d00700642d.png
[20181220230735596]: /images/20220403/2ec80961ae414ba0b265c79e1318a43e.png
[20181220230735613]: /images/20220403/5c081c76ef3a4bb0b81058041a11f01b.png
[20181220230735732]: /images/20220403/e472171472e042d2a47444508c754477.png
[20181220230735815]: /images/20220403/d9f4b514521d4d6ab1e9f9389c788011.png
[20181220230735920]: /images/20220403/6e04506bf06049778be54338803424b5.png
[20181220230735936]: /images/20220403/1f315eb3489d44a4a3feec80384a6e75.png
[20181220230735952]: /images/20220403/b2676d6182e8491d9251957d50fcd781.png
[20181220230735968]: /images/20220403/3f89db8cb34b4b6da98203e8bfe0cee0.png
[20181220230735986]: /images/20220403/87813a72119146b2bf52146c302daa13.png
[2018122023073682]: /images/20220403/672b021ea8e647d7b77775f1de4a5fa0.png
[20181220230736178]: /images/20220403/1c1d823534cc44cbb1dca5d3fd762fc9.png
[20181220230736192]: /images/20220403/349c351f244641c5b4511c95d0e6dafb.png
[20181220230736227]: /images/20220403/df81fcd0230c4779a12a9598f05f5963.png
[20181220230736243]: /images/20220403/22da808f19d346a999780cc21571458d.png
[20181220230736316]: /images/20220403/2bd5446a69654b9c8e53412ce88c93b4.png
[20181220230736334]: /images/20220403/c5aabf0db98e4f87807b4c354bdc7060.png
[20181220230736423]: /images/20220403/75002bdb85f0411c87d9768f7a43bd00.png
[20181220230736439]: /images/20220403/2c9704e2776f4675b48cd5126719b91f.png
[20181220230736454]: /images/20220403/b474b74691864af08629c70e446f1b94.png
[20181220230736471]: /images/20220403/3859e1e467ef451a8fe2968103b31d67.png
[20181220230736489]: /images/20220403/60f18033f9e34eb1934fef07673adb0c.png
[20181220230736511]: /images/20220403/9789c975098649f8b7b03a2fae5f8c07.png
[20181220230736537]: /images/20220403/0343c854f81b41d9b349448a9f660668.png
[20181220230736550]: /images/20220403/9d320648a8fc4983b3c80eb07d793539.png
[20181220230736636]: /images/20220403/4a5281ae509f4af6a707fff9ea2a6599.png
[20181220230736656]: /images/20220403/5c61897d29f646c89f804d77f181e52e.png
[20181220230736742]: /images/20220403/47500922a5744a18844ae0d7c9ccf84f.png
[20181220230736763]: /images/20220403/92a8ee23438c4c318c2bcdbbc4d95d7f.png
[20181220230736844]: /images/20220403/0552b6696e1b4a7fbdbd8ae999979e75.png
[20181220230736860]: /images/20220403/e1996c1720ed49799a3e99e9898a2734.png
[20181220230736945]: /images/20220403/091351a298ee4b928834ce126aade741.png
[20181220230736965]: /images/20220403/7576a83200c945f7b2ed81baa4b5ca58.png
[20181220230736983]: /images/20220403/c0909a68dc114db19237ca973e74f2d2.png
[201812202307370]: /images/20220403/824a8fe722ca4b39b61df267add6dae7.png
[2018122023073716]: /images/20220403/40ce202fe864443583585c1b126e7904.png
[2018122023073732]: /images/20220403/9fcbf710aad2480d8137e9ac396a8279.png
[20181220230737123]: /images/20220403/b9f3656d0956495eba5f1d7e653cbf14.png
[20181220230737137]: /images/20220403/5fd9bb2eed0c46a98e3262966b328d0e.png
[20181220230737245]: /images/20220403/126fd3cf6bc2455ca62204b058c87c54.png
[20181220230737261]: /images/20220403/950b661aaf1f4f55a94b08090bed01a7.png
[20181220230737277]: /images/20220403/44faddc916464a398a0fe4921efce8df.png
[20181220230737293]: /images/20220403/86250e57bb0e4c4aba5acc5805a7d99c.png
[20181220230737311]: /images/20220403/64df946bcd2c4a47b2bf683b73c30674.png
[20181220230737333]: /images/20220403/f125c70c4b994f4d917192b23971df83.png
[20181220230737352]: /images/20220403/3d3e29c83b18482ab44d50106ba627ee.png
[20181220230737370]: /images/20220403/142930ab3ca0464e84e3b25561a51c78.png
[20181220230737392]: /images/20220403/4cd55276b78c42919235912a7a069057.png
[20181220230737409]: /images/20220403/a4342f8621fe45069cac2b693bfbef05.png
[20181220230737430]: /images/20220403/09eb74a0aeed4f0fac0af20069699418.png
[20181220230737448]: /images/20220403/e15a0ad46dab4c558f9d8b4224ac611c.png
[20181220230737465]: /images/20220403/c3591b003d4b400985330c97cabc8028.png
[20181220230737497]: /images/20220403/929f305306bf49b79199163a9479f81d.png
[20181220230737512]: /images/20220403/59abd0066b83454a8eec2bbae7a5eb2a.png
[20181220230737530]: /images/20220403/838dbe28f44347cb9cf437e58d9a5033.png
[20181220230737551]: /images/20220403/b531ce938e2f408cb5fcfe8363ea3578.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485981&idx=1&sn=421b2435ef544c53445b6dd7c1bb804c&chksm=fe795bc5c90ed2d33b4bf23ed1b9741f0bdee39ada5c0687918f80b4b47dff97005f1b36a6c5&scene=21#wechat_redirect
[10_1000]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485898&idx=1&sn=32add192ba3b54c79de6144711a6e5e9&chksm=fe795812c90ed104325a945631c2e2e82af195b312be09a85b1414fe8b356f27698557a61e0e&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzU5NTAzNjM0Mw==&mid=2247485720&idx=2&sn=92a3c7573b1724ebcf2fbc2f7d184c8a&chksm=fe7958c0c90ed1d628b10e9b25189e1f334f366e940508dce599e0ee5b00e8ab5d2005b3cae6&scene=21#wechat_redirect
[70]: /images/20220403/8889b8df82344a80aa555ad2372c7744.png