漫画：如何找到字符串中的最长回文子串？

你的名字 2021-11-10 02:06 298阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | channingbreeze

来源 | 互联网侦察

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

**【面试现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

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

例如

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

输入adaelele，输出应该是elele

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

半分钟过去了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 21]

一分钟过去了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 22]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 23]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 24]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 25]

**【请教大神】**

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 26]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 27]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 28]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 29]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 30]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 31]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 32]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 33]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 34]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 35]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 36]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 37]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 38]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 39]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 40]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 41]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 42]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 43]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 44]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 45]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 46]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 47]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 48]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 49]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 50]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 51]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 52]

小史：当然可以。

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

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

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

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

**【编码实现】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 53]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 54]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 55]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 56]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 57]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 58]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 59]

小史：

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

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

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

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 60]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 61]

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

PlalindromeString.java

/**
     * @author xiaoshi on 2018/9/24.
     * Happy Mid-Autumn Festival
     */
    public class PlalindromeString {
         
    
        // 判断一个字符串是否回文，算法中用不到了
        @Deprecated
        private boolean isPlalindrome(String s) {
         
            int len = s.length();
            for(int i = 0; i < len / 2; i++) {
         
                if(s.charAt(i) != s.charAt(len - 1 - i)) {
         
                    return false;
                }
            }
            return true;
        }
    
        // 预处理字符串，在两个字符之间加上#
        private String preHandleString(String s) {
         
            StringBuffer sb = new StringBuffer();
            int len = s.length();
            sb.append('#');
            for(int i = 0; i < len; i++) {
         
                sb.append(s.charAt(i));
                sb.append('#');
            }
            return sb.toString();
        }
    
        // 寻找最长回文字串
        public String findLongestPlalindromeString(String s) {
         
            // 先预处理字符串
            String str = preHandleString(s);
            // 处理后的字串长度
            int len = str.length();
            // 右边界
            int rightSide = 0;
            // 右边界对应的回文串中心
            int rightSideCenter = 0;
            // 保存以每个字符为中心的回文长度一半（向下取整）
            int[] halfLenArr = new int[len];
            // 记录回文中心
            int center = 0;
            // 记录最长回文长度
            int longestHalf = 0;
            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 = new StringBuffer();
            for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
         
                sb.append(str.charAt(i));
            }
            return sb.toString();
        }
    
    }

Main.java

/**
     * @author lixin on 2018/9/24.
     */
    public class Main {
        
    
        public static void main(String[] args) {
        
    
            PlalindromeString ps = new PlalindromeString();
    
            String[] testStrArr = new String[] {
        
                "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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 62]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 63]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 64]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 65]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 66]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 67]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 68]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 69]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 70]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 71]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 72]

--------------------

**本文相关阅读推荐：**

[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[一道腾讯面试题：厉害了我的杯][Link 2]

[十大经典排序算法动画与解析，看我就够了][Link 3]

[这或许是东半球分析十大排序算法最好的一篇文章][Link 4]

[面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

[看《长安十二时辰》可以了解哪些算法知识][Link 5]

GitHub 标星 3w+，很全面的算法和数据结构知识

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20211109/d7798eb952ee4f5490ef6870c4b3e3cd.png
[640_wx_fmt_jpeg 1]: /images/20211109/4ef01f9eab1547aaa0709924a0146c19.png
[640_wx_fmt_jpeg 2]: /images/20211109/562d0dd9e7264532a09828de716ed9d5.png
[640_wx_fmt_jpeg 3]: /images/20211109/a66d9da7b8d64fcca74b536d152edb6e.png
[640_wx_fmt_jpeg 4]: /images/20211109/7da970f332a64269ad3f2b12d4734776.png
[640_wx_fmt_jpeg 5]: /images/20211109/46e0f03a04aa4d4bafabfed6a5afbecb.png
[640_wx_fmt_jpeg 6]: /images/20211109/f21d62c50f334d5d9380aee1573769d1.png
[640_wx_fmt_jpeg 7]: /images/20211109/3407257a79a842ba82f5d529f3622fa7.png
[640_wx_fmt_jpeg 8]: /images/20211109/9d14324c72d646d98ded91292ad7937c.png
[640_wx_fmt_jpeg 9]: /images/20211109/9e3b8dbcfd46457c8897e68a2f9e29db.png
[640_wx_fmt_jpeg 10]: /images/20211109/2e8d61477dfa48a386301abee9532a48.png
[640_wx_fmt_jpeg 11]: /images/20211109/fe8e03af741c4c05b2867e4f0d586865.png
[640_wx_fmt_jpeg 12]: /images/20211109/a2272273f4f64d92848e9ec5812a5641.png
[640_wx_fmt_jpeg 13]: /images/20211109/4355e2c662ec46fe9780880762b5eaa5.png
[640_wx_fmt_jpeg 14]: /images/20211109/aa7bfed2362142d29c0c911d0fe26a4f.png
[640_wx_fmt_jpeg 15]: /images/20211109/e0fd8cd31a3543ac9d05fe142a23f08d.png
[640_wx_fmt_jpeg 16]: /images/20211109/7db8717c68ac494cb44524999967cb91.png
[640_wx_fmt_jpeg 17]: /images/20211109/111c16527fde45bcad403e805aea4597.png
[640_wx_fmt_jpeg 18]: /images/20211109/37b47a9b025f488fa6e35fec6d71f6ff.png
[640_wx_fmt_jpeg 19]: /images/20211109/13c294a6a69844d9996816fde2ee3cbd.png
[640_wx_fmt_jpeg 20]: /images/20211109/d2f3062e6ce648b8b8fd77a476fe07a2.png
[640_wx_fmt_jpeg 21]: /images/20211109/75c59172abd14e00b8904f9d838ed825.png
[640_wx_fmt_jpeg 22]: /images/20211109/f91d6c34ab6f42a9b5cc5f6b875276b9.png
[640_wx_fmt_jpeg 23]: /images/20211109/fb0e09b8c0234ef29ffab21e9bfacaa0.png
[640_wx_fmt_jpeg 24]: /images/20211109/411f67ae30274aeaae477c2d08a738ff.png
[640_wx_fmt_jpeg 25]: /images/20211109/0294feee4fc04774a9dc1c07ce77d36a.png
[640_wx_fmt_jpeg 26]: /images/20211109/22017a5fd5df4df0a43e1ec8ca6ff03b.png
[640_wx_fmt_jpeg 27]: /images/20211109/0d172d10b08342b8875166d555965749.png
[640_wx_fmt_jpeg 28]: /images/20211109/799fd9db22b04db688e73f4fe096f586.png
[640_wx_fmt_jpeg 29]: /images/20211109/dd7270b92fee499bb05b708ccb6a0296.png
[640_wx_fmt_jpeg 30]: /images/20211109/8ca5e619364d4817832a7f3440c26a3f.png
[640_wx_fmt_jpeg 31]: /images/20211109/05f6b24ef9374f39873ab5cdc952aadc.png
[640_wx_fmt_jpeg 32]: /images/20211109/16ee11ecbc8540c09c773f793c68874c.png
[640_wx_fmt_jpeg 33]: /images/20211109/d70cf6bb79ad4361817aed49bdb0aa20.png
[640_wx_fmt_jpeg 34]: /images/20211109/542ad95bac1641609b339747422d067a.png
[640_wx_fmt_jpeg 35]: /images/20211109/09e7b2c4f5ed45f39c03c69e9599f5f4.png
[640_wx_fmt_jpeg 36]: /images/20211109/92ee9e37383e492d90e935614f8164c8.png
[640_wx_fmt_jpeg 37]: /images/20211109/62f7e30fbaca4309b20c1f9c29cb19c7.png
[640_wx_fmt_jpeg 38]: /images/20211109/1f31850d52a44382a9dcd4ecddacf5a0.png
[640_wx_fmt_jpeg 39]: /images/20211109/2530c92a62e0407fae5101a217f32727.png
[640_wx_fmt_jpeg 40]: /images/20211109/3f7a0b31780c4767907127275078c121.png
[640_wx_fmt_jpeg 41]: /images/20211109/13a865e7676b45c996696e46d69d2b27.png
[640_wx_fmt_jpeg 42]: /images/20211109/5e6be82f08364a1fbe4e3cab8372dbca.png
[640_wx_fmt_jpeg 43]: /images/20211109/0f686e9b8a994725b6351b05025532c8.png
[640_wx_fmt_jpeg 44]: /images/20211109/f2e5503ed1f6482bbb3660d9ab842b22.png
[640_wx_fmt_jpeg 45]: /images/20211109/367e03ca35b34225a99a3ae79f3e5315.png
[640_wx_fmt_jpeg 46]: /images/20211109/89978227a2fe467ab4bbe039485cbe3e.png
[640_wx_fmt_jpeg 47]: /images/20211109/fb990f37641343aa831966987f8ff067.png
[640_wx_fmt_jpeg 48]: /images/20211109/1b96062e326447c38b9671d2ff02b3e7.png
[640_wx_fmt_jpeg 49]: /images/20211109/03178224105949ddb2d770c2a124f172.png
[640_wx_fmt_jpeg 50]: /images/20211109/348990ef2fa4490b9b55c42f344e165d.png
[640_wx_fmt_jpeg 51]: /images/20211109/e1d091a09f034e8aaf4ee183428bf42f.png
[640_wx_fmt_jpeg 52]: /images/20211109/538e55e852b8447b9923a8b8e0f4f05b.png
[640_wx_fmt_jpeg 53]: /images/20211109/02ea7de984d84a098c6006a58e95091d.png
[640_wx_fmt_jpeg 54]: /images/20211109/36026372bfe04b60bd74d64f3d682eb0.png
[640_wx_fmt_jpeg 55]: /images/20211109/ae98803d1cfd439a87847650d5515984.png
[640_wx_fmt_jpeg 56]: /images/20211109/2938c8e2ac8e487dbb14784ab3cfd9ab.png
[640_wx_fmt_jpeg 57]: /images/20211109/c8b76c91eb7d474aadd8f4bd369024da.png
[640_wx_fmt_jpeg 58]: /images/20211109/2ca33d411e64474b8130d620b08b796d.png
[640_wx_fmt_jpeg 59]: /images/20211109/b162f054e8ed4c6ab02945e731ab1473.png
[640_wx_fmt_jpeg 60]: /images/20211109/e2149c4599bf46fa939750f44c292ccb.png
[640_wx_fmt_jpeg 61]: /images/20211109/dd88065723184a88ab1f02e97d98d611.png
[640_wx_fmt_jpeg 62]: /images/20211109/d494af895a2e472b8ff624c2a03fcf6a.png
[640_wx_fmt_jpeg 63]: /images/20211109/6649acd2deff4b56b0269c3dfe86a6f6.png
[640_wx_fmt_jpeg 64]: /images/20211109/d9690202e5c54d9a940c3e0c700532be.png
[640_wx_fmt_jpeg 65]: /images/20211109/2ea56a8df9e74a478498175aa29c8d4a.png
[640_wx_fmt_jpeg 66]: /images/20211109/d34b59576c8343f2bd9ae6465af7540c.png
[640_wx_fmt_jpeg 67]: /images/20211109/54467f25cb2c422fbbb285a5cc15c7c5.png
[640_wx_fmt_jpeg 68]: /images/20211109/c45bf0d006774a2c9f639fd174680509.png
[640_wx_fmt_jpeg 69]: /images/20211109/77583cebe592479a9bd48615d9fca918.png
[640_wx_fmt_jpeg 70]: /images/20211109/d0e7688531da4c2c827e1313f118d61f.png
[640_wx_fmt_jpeg 71]: /images/20211109/9b5a78c32231473ca128235484e67de2.png
[640_wx_fmt_jpeg 72]: /images/20211109/193a60deca0342378ac2cee84954e58c.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 3]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 4]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485904&idx=1&sn=0eae783ce1b7c0383f41d76a269f511e&chksm=fa0e6651cd79ef47d31a0dba6909873974a964e81654cf702e3868da51fa9a695e7b9a383c1a&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20211109/8b416b70fe204c189a5788bf744861b1.png