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);
}
}
