JavaScript求解最长回文子串的方法分享

JS求解最长回文子串的方法分享：

一、前置知识

在学习JS求解最长回文子串之前，你需要掌握以下知识：

1. 严格模式
2. 回文字符串
3. 动态规划

二、什么是回文字符串？

回文字符串是指正着读和倒着读都一样的字符串。例如，'level'、'racecar'、'rotor' 都是回文字符串。

三、求解最长回文子串的方法

对于字符串中的每一个字符，判断它和它往前的字符组成的子串是否是回文字符串，同时记录下最长的回文子串，最后返回最长回文子串的长度。

代码如下：

function longestPalindrome(s) {
    let maxLen = 0;
    let startIndex = 0;
    for (let i = 0; i < s.length; i++) {
        // 判断奇数长度的回文字符串
        let j = i - 1,
            k = i + 1;
        while (j >= 0 && k < s.length && s[j] === s[k]) {
            if (k - j + 1 > maxLen) {
                maxLen = k - j + 1;
                startIndex = j;
            }
            j--;
            k++;
        }
        // 判断偶数长度的回文字符串
        j = i,
        k = i + 1;
        while (j >= 0 && k < s.length && s[j] === s[k]) {
            if (k - j + 1 > maxLen) {
                maxLen = k - j + 1;
                startIndex = j;
            }
            j--;
            k++;
        }
    }

    return s.substr(startIndex, maxLen);
}

示例说明：

• 示例一

console.log(longestPalindrome('babad')) // 'bab'

对于字符串 'babad'，最长的回文子串分别是 'bab' 和 'aba'，返回其中一个即可。

• 示例二：

console.log(longestPalindrome('cbbd')) // 'bb'

对于字符串 'cbbd'，最长的回文子串是 'bb'，直接返回即可。

四、动态规划算法

以上算法的时间复杂度为 $O(n^2)$，还存在一种 $O(n^2)$ 算法，即动态规划算法。

动态规划算法思路和上面的算法一样，但是会多存储一个 $n * n$ 的二维数组 dp 用来记录状态转移，具体实现可参考下面的代码。

function longestPalindromeDP(s) {
    let len = s.length;
    let dp = Array.from({ length: len }, () => Array.from({ length: len }).fill(false));
    let startIndex = 0;
    let maxLen = 1;

    // 初始化单字符和双字符的回文串
    for (let i = 0; i < len; i++) {
        dp[i][i] = true;
        if (i < len - 1 && s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            maxLen = 2;
            startIndex = i;
        }
    }

    // 补充左下角的残缺部分即j-i小于2时的情况
    for (let i = len - 3; i >= 0; i--) {
        for (let j = i + 2; j < len; j++) {
            dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                startIndex = i;
            }
        }
    }

    return s.substr(startIndex, maxLen);
}

五、总结

本文主要介绍了 JS 求解最长回文子串的方法，主要采用了中心扩展和动态规划两种算法，希望对大家有所帮助。