题目:给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
中心扩展算法:
回文中心的两侧互为镜像。因此,回文可以从它的中心展开,由于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba” 的中心在两个‘b’ 之间)。因此,有 2n −1 个这样的中心。
代码如下:
public class day04 {
public static void main(String[]args){
String str="nxlcuisdsdb";
String result=longestPalindrome(str);
System.out.println(result);
}
private static String longestPalindrome(String str) {
if(str==null || str.length()<1) return "";
if(str.length()==1)return str;
int start=0;int end=0;
for(int i=0;i<str.length();i++){
int len1=Center(str,i,i);
int len2=Center(str,i,i+1);
int len=Math.max(len1,len2);
if(len>end-start){
start=i-(len-1)/2;
end=i+len/2;
}
}
return str.substring(start,end+1);
}
private static int Center(String str, int left, int right) {
int l=left;int r=right;
while(l>=0 && r<str.length() && str.charAt(l)==str.charAt(r)){
l--;
r++;
}
return r-l-1;
}
}
时间复杂度为 O(n^2),空间复杂度:O(1)。