這道題常規(guī)做法，從任意位置向兩邊掃描，http://www.programcreek.com/2013/12/leetcode-solution-of-longest-palindromic-substring-java/
的解釋非常容易懂。

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0) return null;
        int maxLength = 1;
        String longestPalindrome = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String temp = helper(s, i, i);
            if (temp.length() > longestPalindrome.length()) {
                longestPalindrome = temp;
            }
        }
        for (int i = 0; i < s.length(); i++) {
            String temp = helper(s, i, i + 1);
            if (temp.length() > longestPalindrome.length()) {
                longestPalindrome = temp;
            }
        }

        return longestPalindrome;
    }

    private String helper(String s, int begin, int end) {
        while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
//注意substring的用法，"babad"的substring(0,2)是"ba"，所以這里end不用-1
        return s.substring(begin+1, end);
    }
}

第二種做法DP，思維難度也不大，狀態(tài)轉(zhuǎn)移方程：

                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;

但是做起來花了很多時(shí)間，首先要知道，這里只需要管上三角矩陣的值，因?yàn)閖>=i的。我甚至連上三角矩陣的判斷方法都想不明白。。思維遲鈍。有點(diǎn)失望。其次，i要從后往前掃，否則會(huì)出現(xiàn)一種情況，aaaa，從0到4的過程中要用到從2到3，如果i從0開始，內(nèi)層的就還沒有檢查過。

DP的復(fù)雜度也是O(n*n)。
好fin，這題搞了三小時(shí)，我真覺得不可思議，就坐在這電腦前3小時(shí)。?？催@dp。。第一種方法做出來之后注意力不集中了。

http://blog.csdn.net/linhuanmars/article/details/20888595