016-最长回文子串 (Longest Palindromic Substring)

题目描述

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

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

示例

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

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

解题思路

使用中心扩展法，遍历字符串的每个位置，以该位置为中心向两边扩展，寻找最长的回文子串。需要同时考虑奇数长度和偶数长度的回文串。

JavaScript 解决方案

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s) => {
    if (s.length < 2) return s;
    
    let start = 0;
    let maxLength = 1;
    
    // 中心扩展函数
    const expandAroundCenter = (left, right) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            const currentLength = right - left + 1;
            if (currentLength > maxLength) {
                start = left;
                maxLength = currentLength;
            }
            left--;
            right++;
        }
    };
    
    // 遍历每个位置作为中心
    for (let i = 0; i < s.length; i++) {
        // 奇数长度的回文串
        expandAroundCenter(i, i);
        // 偶数长度的回文串
        expandAroundCenter(i, i + 1);
    }
    
    return s.substring(start, start + maxLength);
};

复杂度分析

时间复杂度：O(n²)，其中 n 是字符串长度
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 测试函数
const testLongestPalindrome = () => {
    const testCases = [
        {
            s: "babad",
            expected: "bab"
        },
        {
            s: "cbbd",
            expected: "bb"
        },
        {
            s: "a",
            expected: "a"
        },
        {
            s: "ac",
            expected: "a"
        },
        {
            s: "aaaa",
            expected: "aaaa"
        },
        {
            s: "abcba",
            expected: "abcba"
        },
        {
            s: "racecar",
            expected: "racecar"
        },
        {
            s: "abacdfgdcaba",
            expected: "aba"
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = longestPalindrome(testCase.s);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: s = "${testCase.s}"`);
        console.log(`期望: "${testCase.expected}", 实际: "${result}"\n`);
    });
};

// 运行测试
testLongestPalindrome();

关键点总结

中心扩展法：以每个位置为中心向两边扩展
奇偶处理：同时考虑奇数长度和偶数长度的回文串
边界检查：确保扩展时不会越界
长度更新：实时更新最长回文串的起始位置和长度
字符比较：比较左右两边的字符是否相等

总结

这道题考察了以下重点：

中心扩展技巧：理解回文串的对称性质
字符串处理：如何高效地处理字符串子串
边界处理：对字符串边界和特殊情况的处理
算法优化：通过中心扩展避免重复计算

中心扩展法是最优解，时间复杂度为 O(n²)，空间复杂度为 O(1)。在实际面试中，建议先提出动态规划解法，然后优化到中心扩展解法。

016-最长回文子串 (Longest Palindromic Substring)

On this page