5.6如何寻找最长回文子串

5.6 如何寻找最长回文子串

5.6.1 问题分析

给你一个字符串 s，找到 s 中最长的回文子串。

• 一般来说，由于回文串结构的特殊性，解决这种问题的核心是双指针

样例分析:输入s=acaba,那么算法应该要返回aca或者aba

当拿到题目没有思路的时候，不妨先从局部入手，从局部逐步推导达到最优解

• 给定一个字符串s，如何在s中找到一个回文子串?既然回文串是一个正着读和反着读都是一样的字符串，那么如果把s反转,我们称为s'，然后在s和s'中寻找最长公共子串，这样应该就能找到最长的回文子串
  • 这个思路的思维点:
  • 首先抓住回文串正着读和反着读的这个特点，假如我们将raw字符串给反转，那么存在于raw字符串中的回文子串，一定也存在于raw'之中，而且两者一模一样
  • 其次，我们要寻找最长的回文子串，那么只需要找两个字符串的最长公共子串就可以了
• 这个思路听起来似乎很有道理，但是其实对于回文串的定义的识别是不准确的，我们给出两个样例:aacxycaa，它反转之后是aacyxcaa，我们使用算法寻找出其最长公共子串是aac或者caa
• 这显然不符合回文串的规定，回到最原始的定义，正着读和反着读都一样，那么上面这个思路为什么错呢?这是因为这个思路扩大了回文串的定义范围，一个解决办法是找出所有的公共子串，然后使用回文串判别算法来一个个筛选,但是很显然，时间复杂度要达到O(N^2)

5.6.2 正确思路

• 寻找回文串的核心思想:从中间开始向两边扩散来判断回文串

for(int i = 0;i<s.length();i++){
    //找到以s[i]为中心的会问串
    //根据找到的回文串长度来更新答案
}
1
2
3
4

for(int i = 0;i<s.length();i++){
    //找到以s[i]为中心的回文串
    //找到以s[i]和s[i+1]为中心的回文串[i+1]可能越界
   	//更新答案
}
1
2
3
4
5

5.6.3 代码实现

    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0;i<s.length();i++){
            String s1 = palindrome(s, i, i);
            String s2 = palindrome(s, i, i + 1);
            res = res.length()>s1.length()?res:s1;
            res = res.length()>s2.length()?res:s2;
        }
        return res;
    }
    //从s[l]和s[r]开始向两端扩散
    //返回以s[l]和s[r]为中心的最长回文串
    //同时传入l和r,便于处理中心点不在同一个点的情况
    //当l和r相等的时候,就是在寻找长度为奇数的回文串
    //当r=l+1的时候,就是在寻找长度为偶数的回文串
    private String palindrome(String s,int l,int r){
        //防止索引越界
        while (l>=0 && r<s.length() && s.charAt(l) == s.charAt(r)){
            l--;r++;
        }
        return s.substring(l+1,r);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22