Medium
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba"
is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
这道题让我隐约想起之前的一道Edit distance,然而那道题具体细节已经记不清。本题用动态规划,状态方程table[i][j]代表s[i, j]是否为palindrome. 我们先初始化table[i][i] = true,因为所有的单字符都是palindrome, 然后再看长度为2的子串,如果s.charAt(i) = s.charAt(i + 1), 则table[i][i + 1] = true.
然后我们再来看状态转换方程,很容易想到s[i, j] = true if (s[i+1, j - 1] == true && s.charAt(i) == s.charAt(j)). 因为我们要根据i + 1行的元素来推导i行,所以我们先初始化下面的行,于是从最后一行开始。这点也是debug发现的,比如abcba这个字符串,如果我们到看table[0][4],也就是判断abcba是不是回文,那么我们要看table[1][3],如何我们是从上到下初始化的,因为还没初始化完第一行,所以肯定第二行还没开始初始化,我们就只能拿到默认的table[1][3] = false的值,这就出问题了,所以我们要从下到上初始化。而且可以发现,我们的table竖着的是字符的起点,横着的是字符的终点,由于终点肯定在起点之后,所以我们最终只会初始化table的右上部分。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] table = new boolean[n][n];
//boolean[i][j] measn whether substring from position i to j (inclusive) is palindrome or not.
for (int i = 0; i < n ; i++){
table[i][i] = true;
}
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)){
table[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] == true){
table[i][j] = true;
if (j - i + 1 > maxLen){
maxLen = j - i + 1;
start = i;
end = j;
}
}
}
}
return s.substring(start, end + 1);
}
}