描述:
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
分析:
通过代码:
public String longestPalindrome(String s) {
int max = 0;
String va = "";
if (s.length() > 0)
va = s.charAt(0) + "";
for (int i = 0; i < s.length() - 1; i++) {
int l = i, r = i;//奇数个回文串
while (l >= 0 && r <= s.length() - 1) {
if (s.charAt(l) == s.charAt(r)) {
l--;
r++;
} else {
break;
}
}
if (r - l + 1 > max) {
max = r - l + 1;
va = s.substring(l+1, r );
}
l = i;r = i + 1;//偶数个回文串
if (s.charAt(i) == s.charAt(i + 1)) {
while (l >= 0 && r <= s.length() - 1) {
if (s.charAt(l) == s.charAt(r)) {
l--;
r++;
} else {
break;
}
}
}
if (r - l + 1 > max) {
max = r - l + 1;
va = s.substring(l+1, r );
}
}
return va;
}
求最长回文串,能不能有什么优化的方案呢?
首先,最长可能出现在哪里呢?
在这里插入图片描述
如果第一次就找到这个最大的长度了,那么还需要查找其他不可能比它长的回文串了嘛?
使用什么方法能够确定不需要再查找更短的回文串了呢?
在这里插入图片描述
不过在具体的代码实现方面,要注意一些界限、特殊情况。ac代码为:
// 法二,中间扩散
public static String getmaxhuiwen(int l,int r,String s) {
if(l>r)return"";
while (l >= 0 && r <= s.length() - 1) {
if (s.charAt(l) == s.charAt(r)) {
l--;
r++;
} else {
break;
}
}
return s.substring(l+1, r);
}
public static String longestPalindrome(String s) {
int max = 0;
String va = "";
if(s.length()<2)return s;//""和"a"
int mid = (s.length()-1) / 2;//中间(偶数左侧,奇数中间)
for (int i = 0; i < mid+1; i++) {
int l = mid - i, r = l;//左奇数个
String s1=getmaxhuiwen(l, r, s);
va=va.length()>s1.length()?va:s1;
l=mid-i;r=l+1;//左偶数个
s1=getmaxhuiwen(l, r, s);
va=va.length()>s1.length()?va:s1;
l=mid+i;r=l;//右奇数个
s1=getmaxhuiwen(l, r, s);
va=va.length()>s1.length()?va:s1;
l=mid+i;r=l+1;//右偶数个
s1=getmaxhuiwen(l, r, s);
va=va.length()>s1.length()?va:s1;
max=va.length();//最大回文长度
if(max>(mid-i+1)*2)//找不到更长直接返回
{
break;
}
}
return va;
}
这种情况效率已经不错了:
在这里插入图片描述
至于题解区有人提出动态规划的方法,但是动态规划在这题并没有太好的效率提高。这里就不作介绍了。
还有求回文串的马拉车算法,后面会专门写一篇记录学习和理解,敬请关注!