最长回文子串

🟡 中等

题目描述

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

示例 1

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

示例 2

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

示例 3

输入：s = "a"
输出："a"

示例 4

输入：s = "ac"
输出："a"

提示

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

解法一

参考答案 (2 个标签)

暴力枚举 O(n³)

思路

枚举所有子串，判断是否为回文串，记录最长的那个。

代码实现

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
    if (s.length < 2) return s;
    
    let maxLen = 1;
    let begin = 0;
    
    // 判断子串 s[i..j] 是否为回文串
    const isPalindrome = (i, j) => {
        while (i < j) {
            if (s[i] !== s[j]) return false;
            i++;
            j--;
        }
        return true;
    };
    
    for (let i = 0; i < s.length - 1; i++) {
        for (let j = i + 1; j < s.length; j++) {
            if (j - i + 1 > maxLen && isPalindrome(i, j)) {
                maxLen = j - i + 1;
                begin = i;
            }
        }
    }
    
    return s.substring(begin, begin + maxLen);
}

复杂度分析

时间复杂度：O(n³)，枚举子串 O(n²)，判断回文 O(n)
空间复杂度：O(1)

解法二

参考答案 (2 个标签)

中心扩展 O(n²)

思路

回文串具有对称性，可以从中心向两边扩展。回文中心可以是单个字符（奇数长度）或两个字符之间（偶数长度）。

代码实现

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
    if (s.length < 2) return s;
    
    let start = 0;
    let maxLen = 1;
    
    // 从中心向两边扩展，返回回文串长度
    const expandAroundCenter = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        // 返回回文串长度
        return right - left - 1;
    };
    
    for (let i = 0; i < s.length; i++) {
        // 以单个字符为中心（奇数长度）
        const len1 = expandAroundCenter(i, i);
        // 以两个字符之间为中心（偶数长度）
        const len2 = expandAroundCenter(i, i + 1);
        
        const len = Math.max(len1, len2);
        
        if (len > maxLen) {
            maxLen = len;
            // 计算起始位置
            start = i - Math.floor((len - 1) / 2);
        }
    }
    
    return s.substring(start, start + maxLen);
}

复杂度分析

时间复杂度：O(n²)，遍历中心 O(n)，扩展 O(n)
空间复杂度：O(1)

图解中心扩展

字符串: "babad"

以 'a' (索引 1) 为中心：
  奇数扩展: b[a]b → 找到 "bab"
  偶数扩展: a|a → 不匹配

以 'b' (索引 0) 为中心：
  奇数扩展: [b] → 只有 "b"
  偶数扩展: b|a → 不匹配

解法三

参考答案 (2 个标签)

动态规划 O(n²)

思路

定义 dp[i][j] 表示子串 s[i..j] 是否为回文串。状态转移方程：

dp[i][j] = true 当 s[i] === s[j] 且 dp[i+1][j-1] === true
边界条件：单个字符是回文，两个相同字符是回文

代码实现

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
    const n = s.length;
    if (n < 2) return s;
    
    const dp = Array.from({ length: n }, () => new Array(n).fill(false));
    
    let maxLen = 1;
    let start = 0;
    
    // 单个字符都是回文
    for (let i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    
    // 按子串长度枚举
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            
            if (s[i] === s[j]) {
                if (len === 2) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            
            if (dp[i][j] && len > maxLen) {
                maxLen = len;
                start = i;
            }
        }
    }
    
    return s.substring(start, start + maxLen);
}

复杂度分析

时间复杂度：O(n²)
空间复杂度：O(n²)，需要二维数组存储状态

下一章节无重复字符的最长子串