Leetcode 5、最长回文子串

动态规划

• s.charAt(i) == s.charAt(j)

当对于范围为i ~ j的子串是否为回文子串，需要依赖i + 1 ~ j - 1范围内的子串是否是回文子串，即dp[i][j] = dp[i + 1][j - 1];
如果j - i < 2，即i和j是相邻的或者，i == j，dp[i][j] = true

如果dp[i][j] == true，更新maxLen和left。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int maxLen = 0;
        int left = 0;

        for(int i = 0; i < len; i++) {
            dp[i][i] = true;
        }

        for(int i = len - 1; i >= 0; i--) {
            for(int j = i; j < len; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(j - i < 2) {
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }

                if(dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    left = i;
                }
            }
        }

        return s.substring(left, left + maxLen);
    }
}