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"

題目是要找到字符串內(nèi)最大的回文字符串。

首先馬上想到的就是暴力計算(其實應該用dp的，但還是暴力言簡意賅番电，直接莽過去就完事了)堡妒，遍歷計算每個字符的最大的可回文范圍部逮，因為回文包含單數(shù)復數(shù)("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算法博脑，但是看起來有點復雜憎乙，等再研究研究再更新...

未完待續(xù)~