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.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

题目是要找到字符串内最大的回文字符串。

首先马上想到的就是暴力计算(其实应该用dp的，但还是暴力言简意赅，直接莽过去就完事了)，遍历计算每个字符的最大的可回文范围，因为回文包含单数复数("aba"是回文,"aa"也是回文)，因此在计算回文的时候需要，左偏移，不偏移和右偏移分别计算。

时间复杂度在O(n2)，好在时间刚刚好够用没有timelimit

public class longestPalindrome1 {
    static String sr="";

    public static String longestPalindrome(String s) {
        char[] c = s.toCharArray();
        int[] si = new int[c.length];
        String sb = "";
        for(int i=0;i<c.length;i++){
            threeWay(c,i);
        }
        return sr;
    }

    private static void threeWay(char[] c, int a){
        //向左偏移
        int i=a-1,j=a;
        calculation(c,i,j);
        //向右偏移
        i=a;
        j=a+1;
        calculation(c,i,j);
        //不偏移
        i=a;
        j=a;
        calculation(c,i,j);
    }

    private static void calculation(char[] c, int i, int j){
        int len = c.length;
        while(i>=0 && j<len){
            if(isPalindrome(c,i,j) && (j-i+1) > sr.length()){
                char[] ct = new char[j-i+1];
                int ctr=0;
                for(int k=i;k<=j;k++){
                    ct[ctr]=c[k];
                    ctr++;
                }
                sr=new String(ct);
            }
            i--;
            j++;
        }
    }

    private static boolean isPalindrome(char[] c, int i, int j){
        int mid=(j+i)/2;
        int l,r;
        if((j-i)%2==0){
            l=mid;
            r=mid;
        }else {
            l=mid;
            r=mid+1;
        }
        while(i<=l && r<=j){
            if(c[l]!=c[r]){
                return false;
            }
            l--;r++;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(longestPalindrome("cbbd"));
    }
}

但是其实还有更好的方法，使用Manacher算法，但是看起来有点复杂，等再研究研究再更新...

未完待续~