最长回文子串 -岩石教程

找到字符串中的最长回文子串是一道经典的算法题，有多种解法。下面介绍三种常见的解法：动态规划、中心扩展法以及马拉车算法。

方法一：动态规划

使用动态规划的方法，通过构建一个二维数组来记录子串是否为回文。

代码：

function longestPalindrome(s) {
    const n = s.length;
    if (n === 0) return "";

    let longest = "";
    const dp = Array.from({ length: n }, () => Array(n).fill(false));

    for (let len = 1; len <= n; len++) {
        for (let start = 0; start <= n - len; start++) {
            const end = start + len - 1;
            if (s[start] === s[end]) {
                if (len === 1 || len === 2) {
                    dp[start][end] = true;
                } else {
                    dp[start][end] = dp[start + 1][end - 1];
                }
                if (dp[start][end] && len > longest.length) {
                    longest = s.substring(start, end + 1);
                }
            }
        }
    }
    return longest;
}

解释：

初始化二维数组 dp，dp[start][end] 表示子串 s[start...end] 是否为回文。
遍历所有子串长度 len 从1到 n。
对于每个子串 s[start...end]，如果 s[start] === s[end] 且子串 s[start+1...end-1] 是回文，则 s[start...end] 也是回文。
更新最长的回文子串。

时间复杂度：O(n^2)，因为我们遍历了所有子串。

空间复杂度：O(n^2)，因为我们使用了二维数组。

方法二：中心扩展法

中心扩展法通过枚举每一个字符（或每两个字符之间的位置）作为中心，向两边扩展以找到回文。

代码：

function longestPalindrome(s) {
    if (s.length === 0) return "";

    let start = 0, end = 0;

    const expandAroundCenter = (s, 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(s, i, i);
        const len2 = expandAroundCenter(s, i, i + 1);
        const len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }

    return s.substring(start, end + 1);
}

解释：

定义一个辅助函数 expandAroundCenter，以 left 和 right 为中心向两边扩展，返回扩展后的最长回文子串的长度。
遍历每一个字符和每两个字符之间的位置，分别作为中心扩展。
更新最长回文子串的起始和结束位置。

时间复杂度：O(n^2)，因为每个字符都作为中心扩展。

空间复杂度：O(1)，因为只使用了常数级别的额外空间。

方法三：马拉车算法

马拉车算法（Manacher's Algorithm）是一种在线性时间内找到最长回文子串的算法。

代码：

function longestPalindrome(s) {
    if (s.length === 0) return "";

    const T = `#${s.split('').join('#')}#`;
    const n = T.length;
    const P = Array(n).fill(0);
    let C = 0, R = 0;

    for (let i = 1; i < n - 1; i++) {
        const i_mirror = 2 * C - i;
        if (R > i) {
            P[i] = Math.min(R - i, P[i_mirror]);
        } else {
            P[i] = 0;
        }

        while (T[i + 1 + P[i]] === T[i - 1 - P[i]]) {
            P[i]++;
        }

        if (i + P[i] > R) {
            C = i;
            R = i + P[i];
        }
    }

    let maxLen = 0;
    let centerIndex = 0;
    for (let i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }

    const start = (centerIndex - maxLen) / 2;
    return s.substring(start, start + maxLen);
}

解释：

对原字符串进行预处理，在每个字符之间和两端添加特殊字符 #，这样可以将奇数和偶数长度的回文统一处理。
使用数组 P 来记录以每个字符为中心的回文半径长度。
遍历预处理后的字符串 T，通过镜像优化来减少重复计算，并更新当前回文的中心和右边界。
找到 P 数组中最大值对应的中心索引，计算原字符串中的起始位置和最长回文子串。

时间复杂度：O(n)，因为遍历了预处理后的字符串一次。

空间复杂度：O(n)，因为使用了预处理字符串和回文半径数组。

总结

这三种方法各有优劣：

动态规划方法适用于理解回文子串的性质，但时间和空间复杂度较高。
中心扩展方法简单直观，适合一般情况，代码较简洁。
马拉车算法最优，在线性时间内解决问题，但实现复杂。

根据实际需求和字符串长度选择合适的方法。