中等 | 动态规划 |

一. 题目描述

给你一个字符串s，找到 s中最长的回文子串。

二. 题目示例

:::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. 代码

      1. var longestPalindrome = function(s) {
      2. let n = s.length;
      3. let dp = new Array(n);
      4. for(let i=0;i<n;i++){
      5.    dp[i] = new Array(n);
      6. }
      7. let max = {i:0,j:0,len:0};
      8. for(let j=0;j<n;j++){
      9.    for(let i=0;i<=j;i++){
      10.        if(j-i == 0){
      11.            dp[i][j] = true;
      12.        }else if(j-i == 1){
      13.            dp[i][j] = s[i]==s[j];
      14.        }else{
      15.            dp[i][j] = dp[i+1][j-1] && s[i]==s[j];
      16.        }
      17.        if(dp[i][j] && (j-i+1)>max.len){
      18.            max.i = i;
      19.            max.j = j;
      20.            max.len = j-i+1;
      21.        }
      22.    }
      23. }
      24. return s.substring(max.i,max.j+1);
      25. };