面试热题（最长回文子串）

叁歲伎倆 2023-10-14 13:23 6阅读 0赞

> 给你一个字符串 `s`，找到 `s` 中最长的回文子串。
> 
> 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串
> 
>     输入：s = "babad"
>     输出："bab"

最长回文子串以前的博客已经讲过KMP算法以及比较不常见的Manacher算法，这两种两种算法都是比较经典的算法，如果有小伙伴想学习的欢迎浏览[字符串算法][Link 1]，接下来我们会用其他的方式解决这道题目（相对于字符串专业算法来说，这种方式比较好记）

首先我们要知道什么是回文串？

*  一个字符肯定是回文串

![f8a54fd9c1c54677b47cdc458542a85d.png][]

*  字符的个数都是偶数的字符串可以组成回文串

![bd335989ab7242abb351b687ad6dde82.png][]

\---------------------------------------------------------------------------------------------------------------------------------

![88c3333838c74c02852722788e1f38dc.png][]

这种虽然字符的个数都是偶数但是仍然不是回文串

*  至多有一个字符的个数是奇数的字符串可以组成回文串

![130af1b282044d03b8e82f7724637871.png][]

今天我们用的方法时暴力枚举+中心扩散方法，通俗的来说就是枚举字符串中每一个字符作为回文串中心的情况，然后取最max的一种情况作为我们的结果

for(int l=0;l<s.length();l++){
               String res1=...
               String res2=...
               max=max.length()>res1.length()?max:res1;
               max=max.length()>res2.length()?max:res2;
           }

在回文串中，我们的中心字符可能是1个也有可能是2个，那这样我们应该怎么去表示？

![924e7011f9d74cf9979a797449831677.png][]

String res1=find(s,l,l);
    String res2=find(s,l,l+1);

我们的find函数的作用又是什么呢？不就是以中心字符为中心，去向两边扩展，找到最长的回文子串

**回文中心只有一个字符**：

![bda2b6b9647f44079b27cd8bc1b6e12a.png][]

**回文中心只有两个字符**：![75a6b84cf3f844559f6068b730415dd8.png][]

public String find(String s,int left,int right){
            if(left>right){
                return "";
            }
            while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
                left--;
                right++;
            }
           //因为是左开右开，所以截取时是left+1;
            return s.substring(left+1,right);
        }

[Link 1]: https://blog.csdn.net/dfdbb6b/article/details/131555516?spm=1001.2014.3001.5502
[f8a54fd9c1c54677b47cdc458542a85d.png]: https://img-blog.csdnimg.cn/f8a54fd9c1c54677b47cdc458542a85d.png
[bd335989ab7242abb351b687ad6dde82.png]: https://img-blog.csdnimg.cn/bd335989ab7242abb351b687ad6dde82.png
[88c3333838c74c02852722788e1f38dc.png]: https://img-blog.csdnimg.cn/88c3333838c74c02852722788e1f38dc.png
[130af1b282044d03b8e82f7724637871.png]: https://img-blog.csdnimg.cn/130af1b282044d03b8e82f7724637871.png
[924e7011f9d74cf9979a797449831677.png]: https://img-blog.csdnimg.cn/924e7011f9d74cf9979a797449831677.png
[bda2b6b9647f44079b27cd8bc1b6e12a.png]: https://img-blog.csdnimg.cn/bda2b6b9647f44079b27cd8bc1b6e12a.png
[75a6b84cf3f844559f6068b730415dd8.png]: https://img-blog.csdnimg.cn/75a6b84cf3f844559f6068b730415dd8.png