二刷5. Longest Palindromic Substring

Medium
处理情况有三种， 处理方法本质上是一种动态规划，现在的状态取决于前一个状态

• Substring长度为1的都是palindrome

• 长度为2的就判断两个char是不是相等就行
  上面两个相当于动归的base case

• 长度大于2时就要根据charAt(i) == charAt(j) && isPalindrome(i, j)来确定了

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0){
            return "";
        }
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++){
            isPalindrome[i][i] = true;
        }
        // "cbbd"
        //    c  b  b  d  
        //c   t  f   
        //b      t  t
        //b         t  f
        //d            t  
                      
        int start = 0;
        int end = 0;
        int maxLen = 1;
        for (int i = 0; i < n - 1; i++){
            if (s.charAt(i) == s.charAt(i + 1)){
                isPalindrome[i][i+1] = true;
                maxLen = 2;
                start = i;
                end = i+1;
            }
        }
        for (int i = n - 1; i >= 0; i--){
            for (int j = i + 1; j < n; j++){
                if (s.charAt(i) == s.charAt(j) && table[i+1][j-1]){
                    isPalindrome[i][j] = true;
                    if (j - i + 1 > maxLen){
                        maxLen = j - i + 1;
                        start = i;
                        end = j;
                    }
                }
            }
        }
        return s.substring(start, end+1);       
    }
}