JavaScript 最长公共子序列 (LCS)

引入最长公共子序列问题

最长公共子序列（Longest Common Subsequence, LCS）问题是一个经典的计算机科学问题。给定两个序列，求出这两个序列的最长公共子序列。子序列指的是从原序列中删除若干个元素后，剩下的元素按照原来的顺序组成的序列。

动态规划解决 LCS

动态规划是解决这类问题的有效方法。首先我们需要定义一个二维数组 dp 来存储子问题的解。假设我们有两个序列 X[0...m-1] 和 Y[0...n-1]，dp[i][j] 表示 X[0...i-1] 和 Y[0...j-1] 的最长公共子序列的长度。

初始化

在初始化时，dp 数组的第一行和第一列都应被设置为0，因为当其中一个序列为空时，它们之间的最长公共子序列长度必然是0。

let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));

状态转移方程

接下来需要根据状态转移方程来填充 dp 数组：

• 如果 X[i-1] == Y[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则，dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])

// www.javascriptcn.com code example
for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
        if (X[i - 1] === Y[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

输出最长公共子序列

得到 dp 数组后，可以通过回溯的方式找到最长公共子序列。从 dp[m][n] 开始，如果 X[i-1] == Y[j-1]，则将该字符加入到结果中，并向左上角移动；否则，向具有较大值的方向移动。

// www.javascriptcn.com code example
function findLCS(X, Y) {
    let m = X.length, n = Y.length;
    let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));

    // 填充 dp 数组
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (X[i - 1] === Y[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // 回溯获取 LCS
    let lcs = '';
    let i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] === Y[j - 1]) {
            lcs = X[i - 1] + lcs;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
    return lcs;
}

// 示例
console.log(findLCS("ABCBDAB", "BDCABA")); // 输出 "BCBA"

性能优化

对于大型数据集，可以考虑使用更高效的算法或数据结构，如二分查找等，以减少时间复杂度。此外，也可以通过空间优化，例如只使用一维数组来保存状态，从而降低空间复杂度。

以上就是使用 JavaScript 实现最长公共子序列的方法，希望对你有所帮助。