首页 > 代码库 > 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.
思路：
刚开始非常天真，以为stringBuilder.reverse() 和stingBuilder通过错位滑行就可以比较了，当然不行！因为最长子串很有可能不是从头开始的。但也可以从头到尾取子串错位滑行比较，但是时间代价太高，pass。
想了好久，终于想到了，可以从每个字符开始，分别将字符前面和后面的字符进行比较，并将统计的结果给存储下来。但是也有可能最长回文子串的字符个数是偶数，这也是一种情况。将以上两种情况求得的结果进行比较，最长的回文子串就给求出来了。
代码：
public String longestPalindrome(String s) {
String str;
if(s==null)
return null;
if(s.length()<=1)
return s;
int len=s.length();
int endIndex=len-1;
int i=0;
int arr1[]=new int[len];
int arr2[]=new int[len];
Arrays.fill(arr1, 0);
Arrays.fill(arr2, 0);
int start=0,end=0,count=0;
for(i=0;i<endIndex;i++)
{
start=i;
end=i+1;
count=0;
while(s.charAt(start)==s.charAt(end))
{
count+=2;
start--;
end++;
if(start<0||end>endIndex)
break;
}
arr1[i]=count;
}
for(i=1;i<endIndex;i++)
{
start=i-1;
end=i+1;
count=1;
while(s.charAt(start)==s.charAt(end))
{
count+=2;
start--;
end++;
if(start<0||end>endIndex)
break;
}
arr2[i]=count;
}
int max1=arr1[0],max1Index=0;
int max2=arr2[0],max2Index=0;
for(i=1;i<len;i++)
{
if(max1<arr1[i])
{
max1=arr1[i];
max1Index=i;
}
if(max2<arr2[i])
{
max2=arr2[i];
max2Index=i;
}
}
if(max1>max2)
str=s.substring(max1Index-max1/2+1, max1Index+max1/2+1);
else if(max1<max2)
str=s.substring(max2Index-max2/2, max2Index+max2/2+1);
else
{
if(max1Index<max2Index)
str=s.substring(max1Index-max1/2+1, max1Index+max1/2+1);
else
str=s.substring(max2Index-max2/2, max2Index+max2/2+1);
}
return str;
}结果：
leetcode_5_Longest Palindromic Substring
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。