最长公共子序列
Longest Common Subsequence
本机进度仅保存在当前浏览器
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度；不存在则返回 0。子序列是从原字符串中删除部分（或不删除）字符而不改变相对顺序形成的新字符串。
示例：text1 = "abcde"，text2 = "ace"，最长公共子序列为 "ace"，输出 3。
解题思路
- 二维状态 dp[i][j]：text1 前 i 个字符与 text2 前 j 个字符的 LCS 长度。
- 末字符相等：dp[i][j] = dp[i-1][j-1] + 1；不等：两侧分别退一位取较大值。
- 滚动数组可把空间压到 O(min(m, n))，注意用临时变量保存左上角状态。
参考实现
查看参考实现Python · 建议先自行作答
def longestCommonSubsequence(t1, t2):
m, n = len(t1), len(t2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if t1[i - 1] == t2[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]