5. Longest Palindromic Substring
Dynamic Programming
class Solution {
public String longestPalindrome(String s) {
// 设f[i][j]为以s[i]开头s[j]结尾的字符串是否为回文字符串
// f[i][j] = f[i + 1, j - 1] && (s[i] == s[j])
if (s == null || s.length() == 0) {
return "";
}
if (s.length() == 1) {
return s;
}
int n = s.length();
boolean[][] f = new boolean[n][n];
// 初始条件:一字符回文(j == i)
for (int i = 0; i < n; i++) {
f[i][i] = true;
}
// 初始条件:二字符回文(j == i + 1)
for (int i = 0, j = 1; j < n; i++, j++) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = true;
}
}
int longestLen = 0;
int longestI = 0;
int longestJ = 0;
for (int i = n - 2; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
// 除去初始条件以外的情况
if (j != i && j != i + 1) {
if (j - 1 >= 0) {
f[i][j] = f[i + 1][j - 1] && (s.charAt(i) == s.charAt(j));
}
}
if (f[i][j]) {
int len = j - i + 1;
if (len > longestLen) {
longestLen = len;
longestI = i;
longestJ = j;
}
}
}
}
return s.substring(longestI, longestJ + 1);
}
}
不得不吐槽一句,这题直接用DP来做有点麻烦!首先两个初始条件你都得想到,除此之外,因为是bottom-up的动态规划,还得考虑计算顺序(画个二维矩阵会更好理解)。