求star

题目#

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

示例 1：

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

示例 2：

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

提示：

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

解题:key:#

①暴力解法#

TIP

记录最长回文子串的长度和起始下标，这样只需要在最后返回的时候进行截取即可，提高性能

时间复杂度: O(n^3)

空间复杂度: O(1)

/**
 * @param {string} s
 * @return {string}
 */
// 验证子串 s[left...right]是否是回文串
var validPalindromic = (s, left, right) => {
    while (left < right) {
        if (s[left] != s[right])
            return false
        left++
        right--
    }
    return true
}
var longestPalindrome = function (s) {
    let len = s.length
    if (len < 2)
        return s
    // 记录最长回文子串的 长度 和 起始下标
    let maxLen = 1
    let begin = 0
    // 枚举所有长度大于1的子串s[i...j]
    for (let i = 0; i < len - 1; i++) {
        for (let j = i + 1; j < len; j++) {
            // 大于当前最长回文子串的长度 且 是回文串
            if (j - i + 1 > maxLen && validPalindromic(s, i, j)) {
                // 更新
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s.substring(begin, begin + maxLen)
};

②动态规划#

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let len = s.length
    if (len < 2) {
        return s
    }
    let maxLen = 1
    let begin = 0
    // dp[i][i]表示 子串s[i...j] 是否是回文串
    let dp = Array.from(new Array(len), () => new Array(len))
    // 初始化长度为1的子串都是回文串
    for (let i = 0; i < len; i++) {
        dp[i][i] = true
    }
	// 先枚举子串长度 从2开始
    for (let L = 2; L <= len; L++) {
        // 枚举左边界
        for (let i = 0; i < len; i++) {
            // 计算右边界 L = j - i + 1
            let j = L + i - 1
            // 右边界越界 退出循环
            if (j >= len) {
                break
            }
            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]
                }
            }
            // 表明子串s[i...j]是回文串，记录长度和起始位置
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s.substring(begin, begin + maxLen)
};

③中心扩展算法#

TIP

枚举回文子串的中心并尝试扩展，直到无法扩展

/**
 * @param {string} s
 * @return {string}
 */
var expandAroundCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] == s[right]) {
        --left
        ++right
    }
    return right - left - 1
}
var longestPalindrome = function (s) {
    const len = s.length
    let maxLen = 1
    let begin = 0
    for (let i = 0; i < len - 1; i++) {
        const oddLen = expandAroundCenter(s,i,i)
        const evenLen = expandAroundCenter(s,i,i+1)
        const curLen = Math.max(oddLen,evenLen)
        if(curLen > maxLen){
            maxLen = curLen
            begin = i - Math.floor((maxLen - 1) / 2);
        }
    }
    return s.substring(begin, begin + maxLen);
};