力扣-5.最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"
解题思路

采用动态规划的思想，数组dp[i][j]用于表示从i到j的字符串是否为回文字符串。初始化dp[i][i]为true，因为单个字符必为回文字符串。随后确定j的取值范围为[1,length-1],i的取值范围为[0,length-2]。当s[i]!=s[j]时,dp[i][j]设为false。相等时判断如果 j - i < 3，即a,aa,aba这三种情况必为回文字符串，可以直接设dp[i][j]为ture。不满足j - i < 3,则dp[i][j]=dp[i+1][j-1]。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var longestPalindrome = function(s) {
    let length = s.length
    if(length <= 1) return s
    let c = Array.from(s) //字符串s转为数组
    //初始化dp
    let dp = new Array(length).fill(false).map(()=>new Array(length).fill(false))
    //
    for(let i = 0;i < length;i ++){
        dp[i][i] = true
    }
    let max = 1
    let start = 0
    for(let j = 1;j < length;j ++){
        for(let i = 0;i < length-1 &&i < j;i ++){
            if(c[i]!=c[j]){
                dp[i][j] = false
            }else{
                if(j - i < 3){
                    dp[i][j] = true
                }else{
                    dp[i][j] = dp[i+1][j-1]
                }
            }
            if(dp[i][j] && j - i + 1 > max){
            max = j - i + 1
            start = i
            }
        } 
    }
    return s.substring(start, start + max)
};