最长回文子串

这道题要求找出字符串中最长的回文子串。注意是子串（连续），不是子序列，返回的是子串本身，不是长度。

回文串就是正着读和反着读一样的字符串，比如 "aba"、"abba"。单个字符也算回文。

最直观的想法

第一次看到这题，我想到的是：枚举所有可能的子串，判断每个是不是回文，取最长的。

两层循环，外层遍历起点，内层遍历终点，对每个子串用双指针判断是否回文。这是最"暴力"的方法：

var longestPalindrome = function(s) {
    let maxLen = 0
    let result = ''
    
    for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (isPalindrome(s, i, j)) {
                const len = j - i + 1
                if (len > maxLen) {
                    maxLen = len
                    result = s.substring(i, j + 1)
                }
            }
        }
    }
    
    return result
}

function isPalindrome(s, left, right) {
    while (left < right) {
        if (s[left] !== s[right]) return false
        left++
        right--
    }
    return true
}

时间复杂度 O(n³)，对于长字符串会超时。

问题在哪？

这个方法做了很多重复计算。比如我们判断 s[0...4] = "abcba" 是否是回文，然后判断 s[1...3] = "bcb" 时，又重新比较了一遍。

而且，回文串有个重要特征：中心对称。如果我们知道 "aba" 是回文，那么 "a" 也一定是回文。如果我们知道 "abba" 是回文，那么 "bb" 也一定是回文。

中心扩展

既然回文是中心对称的，那我们可以从每个可能的"中心"开始，向两边扩展，找到最长的回文。

中心可能是：

• 单个字符（奇数长度回文，比如 "aba" 的中心是 'b'）
• 两个字符之间（偶数长度回文，比如 "abba" 的中心在 'b' 和 'b' 之间）

对每个中心，我们向两边扩展，直到不满足回文条件：

var longestPalindrome = function(s) {
    if (s.length < 2) return s
    
    let start = 0
    let maxLen = 1
    
    for (let i = 0; i < s.length; i++) {
        // 奇数长度：中心是一个字符
        const len1 = expandAroundCenter(s, i, i)
        // 偶数长度：中心是两个字符之间
        const len2 = expandAroundCenter(s, i, i + 1)
        
        const len = Math.max(len1, len2)
        
        if (len > maxLen) {
            maxLen = len
            // 计算起始位置：中心位置 i 减去"半径"
            start = i - Math.floor((len - 1) / 2)
        }
    }
    
    return s.substring(start, start + maxLen)
}

function expandAroundCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--
        right++
    }
    // 循环结束时，left 和 right 已经指向了不满足条件的位置
    // 所以实际回文长度是 (left + 1) 到 (right - 1)，得到(right - 1) - (left + 1) + 1 =  right - left - 1
    return right - left - 1
}

时间复杂度 O(n²)，空间复杂度 O(1)。

动态规划

另一种思路是动态规划。如果我们知道 s[i+1...j-1] 是回文，且 s[i] === s[j]，那么 s[i...j] 也是回文。

用 dp[i][j] 表示 s[i...j] 是否是回文：

• 初始化：单个字符都是回文，dp[i][i] = true
• 状态转移：dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

var longestPalindrome = function(s) {
    const n = s.length
    if (n < 2) return s
    
    const dp = Array(n).fill(0).map(() => Array(n).fill(false))
    let start = 0
    let maxLen = 1
    
    // 初始化：单个字符都是回文
    for (let i = 0; i < n; i++) {
        dp[i][i] = true
    }
    
    // 从长度为 2 的子串开始
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1
            
            if (len === 2) {
                // 长度为 2：只需要检查首尾是否相等
                dp[i][j] = s[i] === s[j]
            } else {
                // 长度大于 2：首尾相等 且 中间是回文
                dp[i][j] = s[i] === s[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²)。

两种方法对比

方法	时间复杂度	空间复杂度	优点	缺点
中心扩展	O(n²)	O(1)	空间效率高，代码简洁	需要处理奇偶两种情况
动态规划	O(n²)	O(n²)	思路清晰，易于理解 DP	空间开销大

实际面试中，中心扩展法更常用，因为空间效率更高。

这道题在考什么？

这道题的核心是回文串的对称性和中心扩展思想。回文串是中心对称的，我们可以从每个可能的中心向两边扩展，找到最长的回文。

动态规划是另一种思路，用已知的小问题的解推导出大问题的解。但在这道题中，中心扩展法更直观，空间效率也更高。

下次遇到类似题目，看到"回文"相关题目，就应该想到中心扩展或 DP。比如回文子串（统计数量）、最长回文子序列（注意是子序列）这些题，思路都是类似的。

记忆要点：

• 回文 = 中心对称
• 中心扩展 = 从中心向两边扩展
• DP = 用已知的小问题解大问题