最长回文子串难在初始化边界和填表方式。
public class Solution{
public int longestPalindrome(String s) {
int n = s.length();
int[][] dp = new int[n][n]; //dp[i][j]为s[i...j]是否为回文串
int ret = 1; //最长回文子串长度为dp二维数组中dp[i][j]为真时i,j距离最大值
//最长回文串难在边界定义和填表过程
//边界两个:dp[i][i]=1,dp[i][i+1]
for (int i = 0; i < n; i++) {
if (i < n - 1) {
dp[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 1 : 0;
if (dp[i][i + 1] == 1) ret = 2; //注意这里就已经出现可能的最大回文子串
}
dp[i][i] = 1;
}
//每次转移都对子串长度减1,但要注意减1后子串的dp是否初始化或被计算过
//简便的方式是枚举子串的长度,因为当前初始化的为dp中所有子串长度为1和2
for (int L = 3; L <= n; L++) {
for (int i = 0; i + L - 1 < n; i++) { //循环终止条件是右端点存在
int j = i + L - 1;
if (s.charAt(i) == s.charAt(j)) { //转移1
dp[i][j] = dp[i + 1][j - 1];
ret = L; //不用比较前一个ret,因为L是逐步递增的,所有ret也逐步递增
} else {
dp[i][j] = 0; //转移2
}
}
}
return ret;
}
}