题目

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

示例 1：

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

• 思路：使用动态规划思想

难点：寻找状态转化方程

• 首先判断边界条件
• 用二维数组记录每一个截取的字串，
• 判断当前字串的 首尾是否相同，如果长度小于3则不用判断上一次的状态，核心代码 dp[i][j] =s.charAt(i)==s.charAt(j) && ((j-i<=2)||dp[i+1][j-1]);
• 当截取的字串长度最大时，可以返回

class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()==0) return s;
        String res ="";
        boolean [][] dp = new boolean[s.length()][s.length()];
        int max =0;
        for (int j=0;j<s.length();j++){
            for(int i=0;i<=j;i++){
                dp[i][j] =s.charAt(i)==s.charAt(j) && ((j-i<=2)||dp[i+1][j-1]);//判断是否为回文字串
                if(dp[i][j]){
                    if(j-i+1>max){//判断是否为最长
                        max =j-i+1;
                        res =s.substring(i,j+1);//找到 回文字串
                    }
                }
            }
        }
            return res;    
    }
}