题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

思路

时间复杂度o(n^{2);空间复杂度o(n}2)
使用动态规划。
定义dp[i][j]=0表示子串已第i开头、第j结尾的子串不是回文串。dp[i][j]=1，表示是回文串。
初始化要做好：dp[i][i] = 1; dp[i][i-1] = 1
dp[i][i-1]是为了处理len=2的情况，这个要结合代码才能明白。
以子串长度作为变量遍历
dp[i][j] = 1的条件是dp[i+1][j-1]=1且str(i) == str(j)。

代码

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return null;

        char[] arr = s.toCharArray();
        int length = arr.length;

        int[][] dp = new int[length][length];

        for(int i = 0; i < length; i++) {
            dp[i][i] = 1;
        }

        for(int i = 1; i < length; i++)
            dp[i][i-1] = 1;
        // for(int i = 0; i < length - 1; i++)
        //  if(arr[i] == arr[i+1])
        //      dp[i][i+1] = 1;

        int start = 0,end = 0,ans = 1;

        for(int len = 2; len <= length; len++) {
            for(int i = 0; i <= length - len; i++) {
                int j = i + len - 1;
                if(arr[i] == arr[j] && dp[i+1][j-1] == 1) {
                    dp[i][j] = 1;
                    if(j - i + 1 > ans) {
                        ans = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }

        return s.substring(start,end+1);
    }
}