LeetCode 5. 最长回文子串

使用动态规划的思想来解决此题。易知如果dp[i][j]是回文子串，那么dp[i - 1][j - 1]必然也是回文子串。因此该题可用区间动态规划的方法来做。

class Solution {
  public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2)
            return s;
        int maxLen = 1, begin = 0;
        boolean[][] dp = new boolean[len][len];
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i++)
            dp[i][i] = true;
        for (int L = 2; L <= len; L++){    //区间长度逐渐增加
            for (int i = 0; i < len; i++){
                int r = L + i - 1;
                if (r >= len)
                    break;
                 if (chars[i] == chars[r]){
                    if (r - i >= 2){
                        dp[i][r] = dp[i + 1][r - 1];
                    }else {
                        dp[i][r] = true;
                    }
                }else {
                    dp[i][r] = false;
                }
                if (r - i + 1 > maxLen && dp[i][r]){
                    maxLen = r - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}