Problem5

题目

原题描述：

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），讲的十分详细。