最长公共子序列
定义两个字符串的 LCS 递推式，填充二维表，并通过回溯表格重建实际的子序列。
最长公共子序列 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是子序列？
字符串的子序列是通过删除一些（也可以不删除）字符形成的，同时不能改变剩余字符的顺序。例如，'ACE' 是 'ABCDE' 的子序列，但 'AEC' 不是（顺序不对）。两个字符串的最长公共子序列（LCS）是同时出现在这两个字符串中的最长子序列。'ABCBDAB' 和 'BDCABA' 的公共 LCS 可以是长度为 4 的 'BCBA' 或 'BDAB'。
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # True推导 LCS 递推式
定义 dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS 长度。如果字符匹配（text1[i-1] == text2[j-1]），就将 LCS 长度加 1：dp[i][j] = dp[i-1][j-1] + 1。如果不匹配，就从两个字符串中分别跳过一个字符，取结果较大者：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。初始条件：dp[0][j] = dp[i][0] = 0（空字符串与任何字符串的 LCS 长度都是 0）。
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2追踪 LCS 表格
对于 text1='ABCD' 和 text2='ACBD'：先将所有值初始化为 0。当字符匹配时（A-A、C-C、处于正确位置的 B-B、D-D），有 dp[i][j] = dp[i-1][j-1] + 1。否则取左侧和上方相邻单元格中的较大值。查看填充完成的表格，可以看到对角线方向的移动对应匹配的字符。最终值 dp[4][4] 就是 LCS 的长度。
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')重建实际的 LCS
要恢复实际的 LCS 字符串，请从 dp[m][n] 开始沿 DP 表回溯。如果 text1[i-1] == text2[j-1]，则该字符属于 LCS——记录它，然后沿对角线移动到 (i-1, j-1)。如果 dp[i-1][j] > dp[i][j-1]，向上移动；否则向左移动。由于回溯是逆序进行的，最后请将收集到的字符反转。这个重建过程的时间复杂度为 O(m+n)。
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDAB空间优化至 O(n)
LCS 表只需要当前行和上一行。您可以使用大小为 n+1 的一维数组，并使用变量 diagonal 保存被覆盖前 dp[i-1][j-1] 中的值。每一行都从左到右迭代。处理每个单元格后，更新后的 dp[j] 保存当前行的值，而您需要在覆盖前将旧值保存到 diagonal 中。
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4LCS 与编辑距离的关系
LCS 与编辑距离（莱文斯坦距离）密切相关。如果您知道 LCS，就可以只使用插入和删除来计算最小编辑距离：edit_dist = m + n - 2 * LCS(s1, s2)。s1 中不属于 LCS 的每个字符都需要一次删除，s2 中不属于 LCS 的每个字符都需要一次插入。这里不计算替换，因为我们只允许插入和删除，但这个公式对相关问题很有用。
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5两个字符串的删除操作
两个字符串的删除操作（LeetCode 583）要求计算使两个字符串相等所需的最少删除次数。保留下来的字符必须构成一个公共子序列，因此您需要让 LCS 尽可能长，并删除其他所有字符。答案是：m + n - 2 * LCS(s1, s2)。这等价于上面的插入/删除编辑距离。用 LCS 来重新表述问题是一种强大的规约技巧。
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4最长公共子串
不要将LCS（子序列）与最长公共子串混淆。子串必须连续，因此如果字符不匹配，计数会重置为 0，而不是取相邻值的最大值。递推关系变为：如果字符匹配，dp[i][j] = dp[i-1][j-1] + 1；否则 dp[i][j] = 0。请记录所有单元格中的最大值。
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)用于序列比较的 LCS
LCS 广泛用于差异比较工具（例如 Unix 的 diff）来比较文件。两个文件之间的编辑脚本由 LCS 推导而来：LCS 中的行保持不变，文件 1 中多出的行会被删除，文件 2 中多出的行会被插入。理解 LCS 有助于您了解版本控制系统如何跟踪更改，以及合并冲突为何会发生。
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)最短公共超序列
最短公共超序列（LeetCode 1092）要求找出一个最短字符串，使 s1 和 s2 都是它的子序列。超序列中每个 LCS 字符只出现一次；两个字符串中不属于 LCS 的字符都必须包含在内。长度 = m + n - LCS(s1, s2)。要进行重建，请使用相同的 LCS 回溯方法，但在不匹配的位置加入两个字符串中的字符。
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCS 的复杂度与面试技巧
经典 LCS 算法的时间复杂度为 O(m×n)，空间复杂度为 O(m×n)，使用滚动数组技巧后，空间复杂度可以降至 O(min(m,n))。面试技巧：(1) 编码前清楚定义 DP 状态表示的含义。(2) 明确区分匹配和不匹配的情况。(3) 如果要求重建序列，请先说明回溯过程，再编写代码。(4) 提及最长递增子序列（LIS）这一相关的一维问题，它可以通过耐心排序在 O(n log n) 时间内解决。
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)快速检查
测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
在本课中，您学习了：LCS 在匹配时使用 dp[i][j] = dp[i-1][j-1]+1，否则使用 max(dp[i-1][j], dp[i][j-1])；实际序列通过在匹配时沿对角线回溯、在不匹配时向较大相邻值的方向回溯来重建；以及LCS 是编辑距离、删除操作、最短公共超序列和差异比较工具的基础。接下来我们将推导编辑距离（莱文斯坦距离）的递推式，在 LCS 框架中加入替换操作。
常见问题解答
「最长公共子序列」课时是免费的吗？
是的 — 「最长公共子序列」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「最长公共子序列」这节课中我会学到什么？
定义两个字符串的 LCS 递推式，填充二维表，并通过回溯表格重建实际的子序列。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「最长公共子序列」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。