Longest Common Subsequence
给你两个字符串，text1 和 text2。字符串的子序列保留其中一些字母的原有顺序，并删除其余字母；保留的字母不必相邻。返回同时是这两个字符串子序列的最长字符串的长度。如果这两个字符串没有共同字母，则返回 0。
函数
- text1string
- 第一个字符串
- text2string
- 第二个字符串
- 返回值integer
- 最长公共子序列的长度
约束条件
1 ≤ text1.length ≤ 10001 ≤ text2.length ≤ 1000- 这两个字符串只包含小写英文字母。
示例
- 输入
- text1 = "stone"text2 = "longest"
- 输出
- 3
- 解释
- o、n、e 在这两个单词中都按这个顺序出现，所以
one是共同部分，长度为 3。字母 s 和 t 在longest中排在最后，在stone中排在最前，所以用它们最多只能得到st。
- 输入
- text1 = "pear"text2 = "reap"
- 输出
- 2
- 解释
- 两个单词中都出现了
ea。在这两个单词中，p 和 r 分别位于ea的两侧，因此它们都无法与它组合，答案是 2。
- 输入
- text1 = "cat"text2 = "dog"
- 输出
- 0
- 解释
- 这两个单词没有共同的字母，因此唯一的公共子序列是空序列，长度为 0。
进阶
你能否返回一个最长公共子序列本身，以及它的长度？
提示
逐个打开提示，每个都会多透露一点。
看看每个字符串的最后一个字母。两个字母相同时，答案有什么特点？两个字母不同时呢？
如果两个字母相同，就将它们配对。剩下的问题与原问题相同，只是两个字符串都去掉了这个字母。如果两个字母不同，那么至少有一个字母不会被使用，所以分别尝试去掉其中一个，并保留更好的答案。
相同的前缀长度组合会一再出现。把每组前缀长度
(i, j)对应的答案存入表中，从空前缀开始，它们的答案是 0，逐行填表，然后读取最后一个单元格中的答案。
题解
贪心匹配会失败：把 cab 中的 c 和 abc 中最后一个 c 配对后，a 和 b 就无处可配了；跳过它则能找到 ab。两个前缀的答案取决于更短前缀的答案，因此用一个 (n+1) × (m+1) 的表，就能一次求出每一对前缀的答案。每一行只读取上一行，所以两行就够了。
使用递归比较首字母
结果正确，但无法在最大的测试中运行完毕
思路
设 lcs(i, j) 表示后缀 text1[i:] 和 text2[j:] 的答案。如果它们的首字母相同，就将它们配对：跳过这对字母的最长公共子序列，可以用这对字母替换它的第一对字母，且长度不会变短。因此，答案是 1 + lcs(i+1, j+1)。
如果字母不同，它们就不能同时使用，因为它们各自的配对会交叉。因此可以丢弃其中一个：max(lcs(i+1, j), lcs(i, j+1))。空后缀的答案是 0。
每次遇到不匹配都会开始两次调用。两个各有 20 个字母且没有共同字母的字符串，就需要大约 2.8 × 10^11 次调用，但不同的 (i, j) 对只有 (n+1) × (m+1) 个，所以几乎每次调用都会重复之前的调用。
算法
- 为从
i和j开始的后缀编写lcs(i, j)。 - 如果
i或j超出对应字符串的末尾，则返回 0。 - 如果
text1[i] == text2[j]，则返回1 + lcs(i+1, j+1)。 - 否则，返回
max(lcs(i+1, j), lcs(i, j+1))。 - 答案是
lcs(0, 0)。
def longestCommonSubsequence(text1, text2):
def lcs(i, j):
# The longest common subsequence of text1[i:] and text2[j:]
if i == len(text1) or j == len(text2):
return 0
if text1[i] == text2[j]:
return 1 + lcs(i + 1, j + 1)
return max(lcs(i + 1, j), lcs(i, j + 1))
return lcs(0, 0)填写前缀表
思路
令 dp[i][j] 表示 text1 的前 i 个字母和 text2 的前 j 个字母对应的答案，因此索引 0 表示空前缀，第 0 行和第 0 列的值都是 0。比较两个前缀的最后一个字母 text1[i-1] 和 text2[j-1]：字母相同则配对，值为 dp[i-1][j-1] + 1；字母不同则舍弃其中一个，取 max(dp[i-1][j], dp[i][j-1])。这就是从末尾开始读取递推关系。
每个单元格都要读取上方、左侧和左上方的单元格，因此按行从左向右填充时，这些单元格总是已经就绪。对于 pear 和 reap，pea 对应的那一行是 [0, 0, 1, 2, 2]；其中 rea 对应的单元格值为 2，因为 a 和 a 相同，所以在 pe 和 re 对应单元格的值上加一。
两个各有 1000 个字母的字符串需要大约 10^6 次常数时间的步骤。
算法
- 创建一个包含
(n+1) × (m+1)个零的表dp。 - 对于
i从 1 到n，以及j从 1 到m，比较text1[i-1]和text2[j-1]。 - 如果匹配，则设置
dp[i][j] = dp[i-1][j-1] + 1。 - 否则，设置
dp[i][j] = max(dp[i-1][j], dp[i][j-1])。 - 返回
dp[n][m]。
def longestCommonSubsequence(text1, text2):
n, m = len(text1), len(text2)
# dp[i][j]: the longest common subsequence of text1[:i] and text2[:j].
# Row 0 and column 0 stay 0: an empty prefix has nothing in common.
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 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])
return dp[n][m]只保留两行
思路
一行计算完成后，就不会再读取它上面的行。用 prev 保存已完成的行，用 cur 保存正在填充的行，并在每行计算完成后交换它们。递推关系和顺序都保持不变。
答案不取决于哪个字符串在前，因此让行沿着较短的字符串展开。这样，每行只包含 min(n, m) + 1 个数字：对于最大的输入，只需 1001 个数字，而不是一百万个单元格，计算步数仍然是 10^6。
算法
- 如果
text2比text1长，就交换它们。 - 创建
prev和cur，每个都包含m + 1个零，其中m是较短字符串的长度。 - 对于
text1中的每个字母，按照表格中的相同规则填充cur[1..m]，并读取上一行对应的prev。 - 交换
prev和cur。 - 返回
prev[m]。
def longestCommonSubsequence(text1, text2):
if len(text2) > len(text1):
text1, text2 = text2, text1 # keep the rows as short as the shorter string
m = len(text2)
# prev[j]: the answer for the previous prefix of text1 and text2[:j]
prev = [0] * (m + 1)
for ch in text1:
cur = [0] * (m + 1)
for j in range(1, m + 1):
if ch == text2[j - 1]:
cur[j] = prev[j - 1] + 1
else:
cur[j] = max(prev[j], cur[j - 1])
prev = cur
return prev[m]
易错点和边界情况
- 混淆表格索引和字符串索引。单元格
dp[i][j]会比较text1[i-1]和text2[j-1]，因为第 0 行表示空前缀。 - 匹配时，把 1 加到
max(dp[i-1][j], dp[i][j-1])上，而不是加到dp[i-1][j-1]上。这样可能会把同一个字母用两次：用aa和a比较时，结果会是 2，而不是 1。 - 写入仍在读取的那一行。使用两行时，上一行的每个值都必须来自
prev，并且cur[0]必须保持为 0。 - 对长度为 1000 个字母的字符串在 Python 中缓存递归结果。调用深度会达到 2000，超过默认上限 1000。
常见问题3
最长公共子序列的时间复杂度是多少？
表格解法的运行时间为 O(n × m)，每对前缀对应一个单元格。完整表格需要 O(n × m) 的内存，使用两行则需要 O(min(n, m))。不使用表格的普通递归需要指数级时间。
最长公共子序列和最长公共子串有什么区别？
子序列可以跳过字母，但必须保持顺序；子字符串则是一段相邻的字母。对于 stone 和 longest，最长公共子序列是 one（3），但最长公共子字符串是 on（2）。子字符串表在不匹配时会将单元格重置为 0，而不是复制相邻单元格的值。
LCS 与 diff 工具和编辑距离有什么关系？
两个版本文件之间的差异会保留它们行的最长公共子序列，并将其他所有行显示为新增或删除。将一个字符串转换为另一个字符串所需的最少插入和删除次数是 n + m - 2 × LCS。编辑距离还允许替换字母，因此需要单独的表格。
def longestCommonSubsequence(text1, text2):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
text1 = "stone" text2 = "longest"
预期输出
3