最长公共子序列问题的Python实现对比及问题排查

问题1：lcs1超时的原因 #

lcs1超时并非因为二维数组的索引操作成本更高，核心原因是空间复杂度带来的缓存命中率差异：

• lcs1使用O(n*m)的二维数组，当输入字符串很长时，数组会占用大量内存，导致CPU缓存无法容纳整个数组，频繁的缓存 miss 会大幅降低访问速度。
• lcs2使用O(min(n,m))的一维数组，内存占用紧凑，数据更易被CPU缓存命中，访问效率更高。
  另外，二维数组的初始化开销（创建大量子列表）也会比一维数组更大，尤其是在n和m都很大的测试用例中，这部分开销会被放大。

问题2：lcs2的错误及通过测试的原因 #

lcs2的错误根源 #

你的lcs2代码中，初始化语句prev = cur = [0] * (len(s2)+1)是引用赋值——prev和cur指向同一个列表对象。这会导致第一次遍历s1的循环中，修改cur[j]的同时也会修改prev[j]（因为是同一个列表），破坏了LCS状态转移中“prev保存上一行结果”的逻辑。

比如在第一次i循环的j迭代中，当你更新cur[j]时，prev[j]也会同步变化，后续j的计算会错误地使用当前行已修改的值，而非上一行的原始值，最终导致结果偏大（就像你的测试用例中得到19，而正确结果是18）。

为何能通过HackerRank测试？ #

这种错误并非在所有场景下都会暴露：

• 部分测试用例的字符串结构特殊（比如两个字符串完全相同、公共子序列是连续子串、或字符串长度较短），错误的计算逻辑恰好得到了正确结果。
• HackerRank的测试用例可能没有覆盖到能触发该错误的边界场景，比如两个字符串互为逆序、或公共子序列分散在不同位置的情况。

修正后的lcs2应该将prev和cur初始化为两个独立的列表：

def lcs2(s1,s2):
    prev = [0] * (len(s2)+1) 
    cur = [0] * (len(s2)+1)  # 分开初始化，避免引用同一对象
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            if s1[i-1] == s2[j-1]:
                cur[j] = prev[j-1]+1
            else:
                cur[j] = prev[j] if prev[j] > cur[j-1] else cur[j-1]
        prev, cur = cur, [0] * (len(s2)+1)
    return prev[-1]

关于lcs3 #

lcs3是正确的空间优化版LCS实现，它通过更紧凑的方式复用数组，逻辑上和标准LCS一致，所以结果和lcs1相同。

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