最长公共子序列(LCS)函数异常求助：结果不符合预期

原代码的核心问题 #

你的代码逻辑完全不符合最长公共子序列（LCS）的定义：
LCS要求子序列字符顺序一致但无需连续，而你的代码是从x的第i个字符开始，在y中从j=i的位置找第一个匹配字符，然后不断把匹配字符追加到temp中，全程没有重置temp的逻辑，也没有处理“回溯尝试其他路径”的情况，导致错误累加字符。

比如输入"abxabc"和"abyabc"时：

• 处理x[0]='a'，在y[0]找到匹配，temp变为['a']
• 处理x[1]='b'，在y[1]找到匹配，temp变为['a','b']
• 处理x[2]='x'，y中从j=2开始找不到匹配，temp保持不变
• 处理x[3]='a'，在y[3]找到匹配，temp追加为['a','b','a']
• 处理x[4]='b'，在y[4]找到匹配，temp追加为['a','b','a','b']
• 处理x[5]='c'，在y[5]找到匹配，temp追加为['a','b','a','b','c']
  最终得到错误的ababc，这根本不是符合要求的LCS。

正确的LCS实现（动态规划法） #

LCS的经典解法是动态规划，通过构建DP表记录子问题的解，再回溯得到结果：

function LCS(x, y) {
    const m = x.length;
    const n = y.length;
    // 创建DP表，dp[i][j]表示x前i个字符和y前j个字符的LCS长度
    const 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]) {
                // 当前字符匹配，LCS长度为前i-1和j-1的长度+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 i = m, j = n;
    const result = [];
    while (i > 0 && j > 0) {
        if (x[i - 1] === y[j - 1]) {
            // 字符匹配，加入结果，同时向左上方移动
            result.push(x[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            // 上方值更大，向上移动
            i--;
        } else {
            // 左侧值更大，向左移动
            j--;
        }
    }

    // 回溯是从后往前收集的，反转后得到正确顺序
    return result.reverse().join('');
}

// 测试验证
console.log(LCS("abxabc", "abyabc")); // 输出 "abc"

代码说明 #

1. DP表构建：dp[i][j]存储x前i个字符和y前j个字符的LCS长度，初始化为0是因为空字符串的LCS长度为0。
2. 填充规则：
   • 若当前字符匹配，说明可以在x前i-1和y前j-1的LCS基础上延长一位。
   • 若不匹配，则取x前i-1和y前j的LCS，或x前i和y前j-1的LCS中的较大值。
3. 回溯过程：从DP表右下角开始，根据字符是否匹配或DP值的来源，反向遍历收集匹配字符，最后反转得到正确顺序的LCS。

内容的提问来源于stack exchange，提问作者suer231232131133