TikTok LCS：前缀状态、滚动行与重建取舍

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 允许跳过元素但保留顺序，不要求连续；示例按字符串 code point 比较，只返回长度。

解题路线

1. dp[i][j] 表示两前缀的最优长度。任一前缀为空时0；末元素相等可共同使用，得到 dp[i-1][j-1]+1，否则至少舍弃其中一个，取上/左最大。
2. 滚动行保存上一行，左到右更新；覆盖前先保存 old，diagonal 保存上一行前一列。这个顺序保证三种依赖都未丢失。
3. 若输出序列需保存决策或采用分治重建；直接回溯一行无法知道历史路径。多解可任取或另约字典序。
4. 公共子串相等时延长、不等时归零，递推完全不同，不能混用。

手动走一遍

"abcde" 与 "ace" 得3，子序列ace；"abc"与"bac"可取ac或bc，长度2。空串与任意串长度0，重复字符需要一对一匹配位置。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def lcs_length(a, b):
    """Subsequence of both sequences; no contiguity requirement."""
    if len(b) > len(a):
        a, b = b, a
    row = [0] * (len(b) + 1)
    for x in a:
        diagonal = 0
        for j, y in enumerate(b, 1):
            old = row[j]
            row[j] = diagonal + 1 if x == y else max(row[j], row[j-1])
            diagonal = old
    return row[-1]

复杂度

O(mn) 时间、O(min(m,n)) 工作空间；完整表回溯 O(mn) 空间，分治重建可降低空间但证明另讲。

易错点与追问

容易失分的边界

• 滚动行 diagonal 更新后再读取。
• 把最长公共子串当 LCS。
• 长度算法承诺自动返回路径。

继续深挖

• 如何重建一个答案？
• 稀疏匹配位置能否更快？