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"
題目分析：返回一個(gè)字符串的最長回文子串。首先明確一下回文串的概念。一個(gè)回文串也就是一個(gè)字符串，它從正著讀和反著讀都是一樣的。例如"aba"就是一個(gè)回文串，"abba"也是回文串，而"abc"則不是。
本題最簡單的想法就是設(shè)置兩個(gè)指針i，j，然后依次判斷i,j位置之中的字符串是否為回文串，這種方法的時(shí)間復(fù)雜度為0(n^2)，且有大量的不必要判斷。
我們還是考慮一次遍歷的情況，設(shè)置一個(gè)指針i，來尋找從i位置往兩邊擴(kuò)展能擴(kuò)的最大回文子串長度，一次遍歷下來就可以得到答案。但是這時(shí)候有個(gè)問題，回文串有可能是奇串也有可能是偶串，如果我們分奇偶來考慮則會(huì)很麻煩。能否將兩種情況合并成一種呢？我們定義函數(shù)findLongestPalidrome(String s, int i, int j),其中i，j為開始搜索時(shí)的起始位置，那么如果為奇數(shù)的情況下令i＝j(luò)問題就引刃而解了，而偶數(shù)情況下我們令j=i+1，查找de終止條件為i，j越界或者s.charAt(i)!=s.charAt(j)。此時(shí)我們可以得到最長的回文子串的開始位置和結(jié)束位置，用兩個(gè)變量記錄下來。然后每一次循環(huán)之后進(jìn)行比較即可。這種情況的復(fù)雜度仍為O(n^2)，但是中間的判斷步驟會(huì)少很多?？梢越七_(dá)到O(n)。

int start = 0;
    int len = 1;

    public String longestPalindrome(String s) {
        if (s == null)
            return null;
        if (s.length() == 1)
            return s;
        for (int i = 0; i < s.length(); i++) {
            findLongestPalidrome(s, i, i);
            findLongestPalidrome(s, i, i + 1);
        }
        return s.substring(start, start + len);     
    }

    private void findLongestPalidrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }
        if (j - i - 1 > len) {          //易錯(cuò)，容易寫成j-i+1
            len = j - i - 1;        
            start = i + 1;
        }
    }