题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"
分析
求解最长回文子串，显然需要知道起始字符串的位置。
令DP[i][j]表示起始位置是i,j的子串的回文长度
则DP[i][j] = str[i] === str[j] ? DP[i+1][j-1] + 2 : 0;
再考虑子串为aca或者bb,时，DP[i][j] = j+1-i;
可以看到DP[i][j]与DP[i+1][j-1]有关，所以遍历时i从大到小，j从小到大。
function solution(str) {
const len = str.length;
let maxStr = str.slice(0,1);
let DP = [];
for(let i=0;i<len;i++) {
DP[i] = [];
DP[i][i] = 1;
}
for(let i=len-2; i>=0; i--) {
for(let j=i+1; j<len; j++) {
if(str[i] === str[j]) {
if(j-i<3) {
DP[i][j] = j+1-i;
} else if(DP[i+1][j-1]) {
DP[i][j] = DP[i+1][j-1] + 2;
}
if(DP[i][j] > maxStr.length ){
maxStr = str.slice(i, j+1);
}
} else {
DP[i][j] = 0;
}
}
}
return maxStr;
}
下面的解法，DP[i][j]中存储当前字符串是否为回文，再使用left, right变量来记录当前最大回文子串的位置。
function solution(str) {
const len = str.length;
let maxLen = 1;
let left = 0;
let right = 1;
let DP = [];
for(let i=0;i<len;i++) {
DP[i] = [];
DP[i][i] = 1;
}
for(let i=len-2; i>=0; i--) {
for(let j=i+1; j<len; j++) {
if(str[i] === str[j] && (j-i<3 || DP[i+1][j-1])) {
DP[i][j] = 1;
if(j-i+1 > maxLen) {
maxLen = j-i+1;
left = i;
right = j;
}
} else {
DP[i][j] = 0;
}
}
}
return str.slice(left, right+1);
}
