中等 | 动态规划 |
一. 题目描述
二. 题目示例
:::tips
输入:s = “babad”
输出:”bab”
:::
:::tips
输入:s = “cbbd”
输出:”bb”
:::
三. 题目解答
1. 思路
- DP数组:
- dp[i][j]代表 i到j是否是回文子串。
- 状态转移方程:
- dp[i][j] = dp[i+1][j-1] && s[i]==s[j],内部串分别向左向右扩散一个位置。
- 初始值和边界条件:
- i≤j。
- 当i==j时,字符串就是字符本身,为true;
- 当i+1 == j时,字符串是i和j两个字符,当二者相等时为true否则为false。
2. 代码
var longestPalindrome = function(s) {
let n = s.length;
let dp = new Array(n);
for(let i=0;i<n;i++){
dp[i] = new Array(n);
}
let max = {i:0,j:0,len:0};
for(let j=0;j<n;j++){
for(let i=0;i<=j;i++){
if(j-i == 0){
dp[i][j] = true;
}else if(j-i == 1){
dp[i][j] = s[i]==s[j];
}else{
dp[i][j] = dp[i+1][j-1] && s[i]==s[j];
}
if(dp[i][j] && (j-i+1)>max.len){
max.i = i;
max.j = j;
max.len = j-i+1;
}
}
}
return s.substring(max.i,max.j+1);
};