題目要求

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
??題目翻譯：給定一個字符串，找到最長的回文字串，假定字符串長度最大為1000，并存在唯一的最大回文子串。

題目分析一

假設(shè)s(j+1,k-1)是一個回文串，且s[j]==s[k]，可證，s(j,k)也一定是一個回文串。由此啟發(fā)，我們可以記錄之前的結(jié)果作為啟發(fā)信息，以利于后面的判斷和搜索。該算法的復(fù)雜度為O(n^2)。

package com.linsiyue;

public class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        int lo = 0,maxLen = 0;
        // 聲明一個boolean型二維數(shù)值，s(j,k)為回文串則boolean[i][j]=true
        // 其中 i<=j
        boolean[][] dp = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                // 關(guān)鍵點(diǎn)是j-i<3這個邊界條件的加入，搜索問題要定義明確邊界條件
                // 當(dāng)字符串長度為1或i=0時，dp[i+1][j-1]會出現(xiàn)數(shù)組越界的錯誤
                // 當(dāng)s.charAt(i)==s.charAt(j) && j-i<3 時，是回文串，如aba,aa
                dp[i][j] = s.charAt(i)==s.charAt(j) && (j-i<3 ||dp[i+1][j-1]);
                if (dp[i][j] && j-i+1>maxLen){
                    lo = i;
                    maxLen = j-i+1;
                }
            }
        }
        return s.substring(lo,lo+maxLen);
    }
}

題目分析二

長度為偶數(shù)的回文串，有如下性質(zhì)：中間的兩個字符s[i]==s[i+1],且s[i-1]==s[i+2]，依次向兩邊對稱遞推，直到碰到回文串邊界。長度為奇數(shù)的回文串，最中間的數(shù)的兩邊的數(shù)相等，即s[i-1]==s[i+1]，隱含著一個重要條件，s[i]==s[i]，有了該隱含條件，遞推模式即如偶數(shù)。
??因此奇偶數(shù)情況可以抽象為一個模型：由中間向兩邊，依次比較軸對稱的兩個字符，直到兩個字符不相等，即可獲得該回文串的起始地址及長度。
??函數(shù)extendPalindrome(String s, int j, int k)即是該模型的實(shí)現(xiàn)。

package com.linsiyue;

public class Solution {
    private int lo, maxLen;
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len<2)
            return s;
        for (int i = 0; i < len-1; i++) {
            // 奇數(shù)情況
            extendPalindrome(s,i,i);
            // 偶數(shù)情況
            extendPalindrome(s,i,i+1);
        }
        return s.substring(lo, lo+maxLen);
    }   
    public void extendPalindrome(String s, int j, int k) {
        while (j>=0 && k<s.length() && s.charAt(j)==s.charAt(k)){
            j--;
            k++;
        }
        // 跳出while循環(huán)時，回文串的開頭和結(jié)尾游標(biāo)分別被-1和+1
        // 因此計算長度的補(bǔ)回：len=(k-1)-(j+1)+1=k-j-1
        if(maxLen < k-j-1){
            lo = j+1;
            maxLen = k-j-1;
        }
    }
}