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]为中心的会问串
//根据找到的回文串长度来更新答案
}
for(int i = 0;i<s.length();i++){
//找到以s[i]为中心的回文串
//找到以s[i]和s[i+1]为中心的回文串[i+1]可能越界
//更新答案
}
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);
}