Heading

5.最长回文子串 (opens new window)

Tags: algorithms amazon bloomberg microsoft string dynamic-programming

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Medium (38.11%)
• Likes: 7101
• Dislikes: -
• Total Accepted: 1.6M
• Total Submissions: 4.3M
• Testcase Example: '"babad"'

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 * 中心扩散
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) {
        return s
    }

    // 以start和end为中心，计算最大回文串的长度
    const maxPalindromeLength = (str, start, end) => {
        while (start >= 0 && end < str.length && str[start] === str[end]) {
            start--
            end++
        }
        return end - start + 1 - 2
    }

    let begin = 0
    let maxLength = 0
    for (let i = 0; i < s.length; i++) {
        // 奇数和偶数分别讨论
        const oddMax = maxPalindromeLength(s, i, i)
        const evenMax = maxPalindromeLength(s, i, i + 1)
        const curMaxLength = Math.max(oddMax, evenMax)
        if (curMaxLength > maxLength) {
            maxLength = curMaxLength
            begin = i - Math.floor((curMaxLength - 1) / 2)
        }
    }
    return s.slice(begin, begin + maxLength)
}
// @lc code=end

// @after-stub-for-debug-begin
module.exports = longestPalindrome
// @after-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=5 lang=javascript
 *
 * [5] 最长回文子串
 * 动态规划
 */

// @lc code=start
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length < 2) {
        return s
    }

    let begin = 0
    let maxLength = 0

    // dp[i][j] 代表下标从i到j是一个回文串
    // dp[i][j] = s[i] === s[j] && dp[i+1][j-1]
    const dp = []
    for (let i = 0; i < s.length; i++) {
        if (dp[i] === undefined) {
            dp[i] = []
        }
        dp[i][i] = true
    }

    for (let j = 1; j < s.length; j++) {
        for (let i = 0; i <= j; i++) {
            if (s[i] !== s[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 > maxLength) {
                maxLength = j - i + 1
                begin = i
            }
        }
    }

    return s.slice(begin, begin + maxLength)
}
// @lc code=end

// @after-stub-for-debug-begin
module.exports = longestPalindrome
// @after-stub-for-debug-end