Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

time space o(n^2);

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) return s;
        
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        int max = 0;
        String res = "";
        
        int[] index = new int[2];
        for(int j = 0; j < s.length();j++){
            for(int i = 0; i <= j; i++ ){
                
                //当i-j范围内字符串收尾字母相同，应该检查其内部是不是回文，通过dp[i-1][j-1]来判断
                //但是当j-i == 2时，i-j之间只有一个字母，一个字母是回文的，,当j-i小于2时，说明i
                // i == j, 不符合要求，所以不要判断，这就是为什么 要先验证 j - i 是不是大等于2
                dp[i][j] = s.charAt(j) == s.charAt(i) && ((j - i <=2)  || dp[i+1][j-1]);
                
                if(dp[i][j]){
                    if(j-i+1 > max){
                        max = j-i+1;
                        index[0] = i;
                        index[1] = j;
                    }
                }
             }
        }
        res = s.substring(index[0],index[1]+1);
        return res;
    }
}