15、最长回文子串

[fudx]

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

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

示例 1：

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

输入：s = "cbbd"
输出："bb"

// todo
var longestPalindrome = function(s) {

};

[fudx]

var longestPalindrome = function(s) {
    const dp = new Array(s.length).fill(0).map(v=> Array(s.length).fill(0))
    for(let i = 0 ; i < s.length; i++) {
        dp[i][i] = 1
    }
    let ans = s[0]
    for(let j = 1; j < s.length; j++) {
        for(let i = j - 1; i >= 0; i--) {
            if(s[i] === s[j] && (dp[i+1][j-1] == 1 || j - i == 1)) {
                dp[i][j] = 1
                if(j - i + 1> ans.length) {
                    ans = s.slice(i,j+1)
                }
            }
        }
    }
    return ans
};

[fudx]

var longestPalindrome = function(s) {
    let maxStr = ''
     const helper = (l,r)=>{
         while(l>=0 && r<=s.length - 1 && s[l] == s[r]) {
             l--
             r++
         }
         const curStr = s.slice(l+1,r)
         if(curStr.length>maxStr.length) {
             maxStr = curStr
         }
     }
     for(let i = 0; i < s.length; i++) {
         helper(i,i)
         helper(i,i+1)
     }
     return maxStr
};

[fudx]

var longestPalindrome = function (s) {
    if(s.length < 2) return s
    let res = ''
    function helper(i,j) {
        while(i>=0 && j< s.length && s[i] === s[j]) {
            i--
            j++
        }
        if(j-i -1 > res.length) { // 多循环一次  所以 i多减了一次。j多加了一次
            res = s.slice(i+1,j)
        }
    }
    for(let i = 0; i < s.length; i++) {
        helper(i,i)
        helper(i,i+1)
    }
    return res
};