一、問題描述
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.

二、解決思路
思路一：暴力法，先求出字符串的全部子字符串，然后對每個子字符串進行判斷，O(n^3)
思路二：動態(tài)規(guī)劃法，可以發(fā)現(xiàn)字符串存在一些規(guī)律，f(i, j) = f(i - 1, j + 1)，當且僅當i - 1和 j + 1字符相同（其中i、j為字符串索引下標），思路一在對每個子字符串進行判斷時，未保存之前判斷的信息，因此可以用空間換時間的思想，使用二維數(shù)組保存之前判斷信息，時空O(n^2)
思路二擴展：思路二算法實現(xiàn)使用了數(shù)組保存的是最長回文子字符串，該思路使用二維數(shù)組存儲下標起止子字符串是否回文字符串，并使用兩變量動態(tài)求出最長回文子字符串
思路三：參考solution方法1，問題是求回文字符，只需求字符串與其翻轉(zhuǎn)字符串的公共最長子字符串（非常巧妙，根據(jù)字符串特征著手），但在求最長子字符串過程中，還需要判斷，時空O(n^2)
思路四：思路二使用了 O(n^2) 空間消耗，還是從回文字符串特點入手，回文字符串左右對稱，因此，可以以一個字符為中心，從左右兩邊進行判斷是否相等，求出最長子字符串，O(n^2)
思路五：參考solution的Manacher's Algorithm，馬拉車算法的核心就兩點：

• 對原字符串進行預處理，使字符串變?yōu)槠鏀?shù)長度
• 還是根據(jù)回文字符串特點，定義一個一維數(shù)組P，用于存放以該字符為中心的回文最長長度，假設下標C的回文最長長度為R（P[C] = R），下標 i 關于C的對稱下標為 i_mirror, i 和 i_mirror有如下關系：P[i] = P[i_mirror]，但有三種情況不滿足上述關系：
  1）i_mirror達到字符串左邊界
  2）P[i_mirror] 超出了C回文范圍
  3）i 等于R
  這三種情況需要通過左右擴展進行計算

三、算法實現(xiàn)
思路二

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        int[][] arr = new int[lens][lens];
        String res = "";
        for (int i = 0; i < lens; i++) {
            arr[i][i] = 1;
            res = chackMaxStr(s, res, arr, i, i);
            res = getLongStr(s, res, arr, i - 1, i + 1, lens);
            //System.out.println(res);
            if((i + 1) < lens) {
                if (s.charAt(i) == s.charAt(i + 1)) {
                    arr[i][i + 1] = 2;
                    // 需要特殊處理
                    res = chackMaxStr(s, res, arr, i, i + 1);
                    res = getLongStr(s, res, arr, i - 1, i + 2, lens);
                } else {
                    arr[i][i + 1] = 1;
                    // 需要特殊處理
                    res = chackMaxStr(s, res, arr, i, i + 1);
                    res = getLongStr(s, res, arr, i, i + 2, lens);
                }
                //System.out.println(res);
            }
        }
        //printArr(arr);
        return res;
    }

    public String chackMaxStr(String s, String cur, int[][] arr, int i, int j){
        String res = cur;
        int max = cur.length();
        if(arr[i][j] > max){
            res = s.substring(i, j + 1);
        }
        return res;
    }

    public String getLongStr(String s, String cur, int[][] arr, int i, int j, int lens){
        String res = cur;
        int max = res.length();
        while(i >= 0 && j < lens){
            if(s.charAt(i) == s.charAt(j)){
                arr[i][j] = arr[i + 1][j - 1] + 2;
                if(arr[i][j] > max){
                    //System.out.println(i + " = " + j + ", " + s.substring(i, j + 1));
                    res = s.substring(i, j + 1);
                    max = arr[i][j];
                }
            } else {
                break;
            }
            i--;
            j++;
        }
        return res;
    }

思路二擴展

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        int start = 0;
        int len = 1;
        // 數(shù)組用于標識下標起止子字符串是否回文字符
        int[][] arr = new int[lens][lens];
        for(int i = 0; i < lens; i++){
            arr[i][i] = 1;
            if((i + 1) < lens){
                if(s.charAt(i) == s.charAt(i + 1)){
                    start = i;
                    arr[i][i + 1] = 1;
                    len = 2;
                }
            }
        }
        // 動態(tài)求出最長回文子串
        for(int i = 3; i <= lens; i++){
            for(int j = 0; j <= lens - i; j++){
                if(s.charAt(j) == s.charAt(j + i - 1) && (arr[j + 1][j + i - 2] == 1)){
                    arr[j][j + i - 1] = arr[j + 1][j + i - 2];
                    start = j;
                    len = i;
                }
            }
        }
        //System.out.println(start + " = " + len);
        String res = s.substring(start, start + len);
        return res;
    }

思路四

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        String res = s.substring(0, 1);
        int i = 1;
        String tmp = "";
        String tmp1 = "";
        while(i < lens){
            // 判斷該字符是否與前字符相同, 分兩種情況分別處理
            if(s.charAt(i) == s.charAt(i - 1)){
                tmp = checkLeftRightStr(i, i, lens, s);
                tmp1 = checkLeftRightStr(i - 1, i, lens, s);
            } else {
                tmp = checkLeftRightStr(i, i, lens, s);
            }
            res = tmp.length() > res.length() ? tmp : res;
            res = tmp1.length() > res.length() ? tmp1 : res;
            i++;
        }
        return res;
    }

    public String checkLeftRightStr(int i, int j, int lens, String s){
        String res = s.substring(i, j + 1);
        i--;
        j++;
        //System.out.println(i + " = " + j);
        while(i >= 0 && j < lens){
            if(s.charAt(i) == s.charAt(j)){
                res = s.substring(i, j + 1);
            } else {
                break;
            }
            i--;
            j++;
            //System.out.println(i + " = " + j);
        }
        return res;
    }

思路五

public String longestPalindrome(String s) {
        int lens = s.length();
        if (lens == 0 || lens == 1) return s;
        // 字符預處理
        StringBuilder sb = new StringBuilder();
        sb.append('#');
        for(int i = 0; i < lens; i++){
            sb.append(s.charAt(i));
            sb.append('#');
        }
        String s1 = sb.toString();
        //System.out.println(s1);
        lens = s1.length();
        // 回文中心下標
        int c = 0;
        // 最長回文長度
        int max = 0;
        int mc = 0;
        // 回文右邊界
        int r = 0;
        int[] arr = new int[lens];
        for(int i = 0; i < lens; i++){
            arr[i] = i < r ? Math.min(arr[2 * c - i], r - i) : 1;
            while((i + arr[i] < lens) && (i - arr[i] >= 0) &&
                    (s1.charAt(i + arr[i]) == s1.charAt(i - arr[i]))){
                arr[i] += 1;
            }
            if(r < (i + arr[i] - 1)){
                r = i + arr[i] - 1;
                c = i;
            }
            if(max < arr[i]){
                max = arr[i] - 1;
                mc = i;
            }
        }
        //System.out.println(c + " = " + r + " = " + mc + " = " + max);
        String res = s1.substring(mc - max + 1, mc + max);
        res = res.replaceAll("#", "");
        return res;
    }