题目
原题描述：
Given a string s, find the longest palindromic substring in s. You may assume that
the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
题目提炼
给定一个字符串，求出其最长的回环子串。
分析
首先解释一下回环串的定义，回环串就是形如：aba、aabbaa这种，正序和逆序都一样的字符串。由此可知，回环串一定是对称的。并且因为要求最长回环子串，所以这里必然有标记每一次结果的变量tmp与标记当前最长子串的变量result。这里给定了一个子串，让我们求出其最长的回环子串，可以从两个角度考虑，
1.一个是先找回环子串的两个端点，然后从两端逼近，这样的好处就是不需要区分子串长度为奇数还是偶数，但是缺点在于需要写三层循环。
算法如下：
1.令字符串为s，选取左端点left=0，右端点right=string.length;
2.比较两个端点的字符是s[left]与s[right]是否相同，如果不相同则right--然后跳到第4步;相同则执
行第3步。
3.令i=left+1;j=ringht-1;比较s[i]与s[j]是否相同，不相同则跳到第5步如果相同则i++,j--然后继续
比较直到s[i]与s[j]不同或者i=j;当i=j时，result=max(result,tmp)
4.ringht--,返回第2步直到right=left;
5.left++，返回第2步，直到s.length-left小于当前最长回环子串长度。
代码如下：
public String solustion(String s){
char[] a=s.toCharArray();
int end=0;
int start=0;
for(int i=0;i<s.length();i++){
char c=a[i];
for(int n=s.length()-1;n>i;n--){
if(c==a[n]) {
char c2=c;
boolean flag=false;
for (int j = n; ; ) {
if (c2 == a[j]) {
j--;
if (j >i) {
c2 = a[n - j+i];
} else {
if((n-i)>(end-start))
{
end=n;
start=i;
flag=true;
}
break;
}
} else {
break;
}
}
if (flag) {
break;
}
}
}
if ((end-start)>s.length()-i)
{
break;
}
}
return s.substring(start,end+1);
}
2.是从回环子串的对称中心开始向两端逼近，这个的好处就是减少了循环次数，但是要判断长度为奇数还是偶数。
public String solution2(String s){
int center=0;
int len=0;
char[] a=s.toCharArray();
for(int i=0;i<a.length;i++)
{
int len1=getlen(a,i,i);
int len2=getlen(a,i,i+1);
int len3=Math.max(len1,len2);
if(len3>len){
len=len3;
center=i;
}
if(len>(a.length-i)*2) {
break;
}
}
return s.substring(center-(len-1)/2,center+len/2+1);
}
private int getlen(char[] s, int left, int right) {
int l = left, r= right;
while (l >= 0 && r < s.length && s[l] == s[r]) {
l--;
r++;
}
return r - l - 1;
}
特记
寻找最长回环字串有一个很出名的算法，叫做（马拉车）算法。他能将时间复杂度降低到O(n)，但是因为这个算法不是一般性的，所以在面试笔试中不会考到，可以作为拓展了解。这个算法可以参考博客（www.cnblogs.com/bitzhuwei/p/Longest-Palindromic-Substring-Part-II.html），讲的十分详细。
