首页 > 代码库 > 【LeetCode】5. Longest Palindromic Substring 最大回文子串
【LeetCode】5. Longest Palindromic Substring 最大回文子串
题目：
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
思路：用Manacher算法得到最大回文子串的长度，得到带#的最大回文子串，用split剔除#后转化成String形式输出即可。
public class Solution {
public String longestPalindrome(String s) {
if(s==null || s.length()==0){
return null;
}
char[] charArr=manacherString(s);
int[] pArr=new int[charArr.length];
int index=-1;
int center=-1;
int pR=-1;
int max=0;
for(int i=0;i<charArr.length;i++){
pArr[i]=pR>i?Math.min(pArr[2*index-i],pR-i):1;
while(i+pArr[i]<charArr.length && i-pArr[i]>-1){
if(charArr[i+pArr[i]]==charArr[i-pArr[i]]){
pArr[i]++;
}else{
break;
}
}
if(i+pArr[i]>pR){
pR=i+pArr[i];
index=i;
}
if(pArr[i]-1>max){
max=pArr[i]-1;//得到最大回文子串的长度
center=i;
}
}
//以string形式返回最大回文子串
String str=new String(charArr);
String[] strArr=str.substring(center-max,center+max).split("#");
StringBuffer sb=new StringBuffer();
for(int i=0;i<strArr.length;i++){
sb.append(strArr[i]);
}
return sb.toString();
}
public static char[] manacherString(String str){
char[] charArr=str.toCharArray();
char[] res=new char[2*str.length()+1];
int index=0;
for(int i=0;i!=res.length;i++){
res[i]=(i&1)==0?‘#‘:charArr[index++];
}
return res;
}
}
【LeetCode】5. Longest Palindromic Substring 最大回文子串
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。