1143. 最长公共子序列 (Medium)
专题归类： 10-动态规划 LeetCode 链接： https://leetcode.cn/problems/longest-common-subsequence/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
示例 1：
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，长度为 3。
示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
提示：
- 1 <= text1.length, text2.length <= 1000
- 字符串仅由小写英文字符组成
题目详细分析
- 数据范围：长度 <= 1000，O(m * n) 的 DP 约 10^6 次操作，可以接受。
- 核心约束：子序列不要求连续但要求相对顺序；“公共”意味着两个字符串共享相同的子序列。
- 边界条件：任一字符串为空时 LCS 长度为 0。
- 隐藏条件：如果两个字符相等，这个字符一定属于 LCS（最优子结构）。这是 LCS 问题的关键性质。
小白版直白理解
你有两串字符，想从每串里各挑出一些字符（按原来的顺序），让挑出来的两串完全相同。就像两个人各有一条彩带，你想从中剪出一样的花纹，且必须保持原有的顺序。“最长公共子序列”就是你能剪出的最长的那段相同花纹。
例如 “abcde” 和 “ace” → 挑 “a”、“c”、“e” 就是最长的公共部分。
解题思路
思路一：二维 DP（推荐）
核心洞察：dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的 LCS 长度。如果 text1[i-1] == text2[j-1]，这个字符计入 LCS；否则从两个字符串各退一个字符的状态中取较大值。
DP 五步法：
- dp 定义：
dp[i][j]表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度 - 递推公式：
- 字符相等：
dp[i][j] = dp[i-1][j-1] + 1 - 字符不等：
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 字符相等：
- 初始化：
dp[0][j] = 0，dp[i][0] = 0 - 遍历顺序：从上到下、从左到右
- 举例验证：text1=“abcde”, text2=“ace” → 见下方表格
"" a c e "" 0 0 0 0 a 0 1 1 1 b 0 1 1 1 c 0 1 2 2 d 0 1 2 2 e 0 1 2 3 ← 答案 3
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
# dp[i][j] 表示 text1[:i] 和 text2[:j] 的 LCS
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]:
# 字符相等，LCS 长度 +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]思路二：空间优化 DP（一维 + 左上角暂存）
每次更新只依赖当前行和上一行，可用一维数组 + 变量保存左上角值。
def longestCommonSubsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0 # 左上角 dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # 保存当前值（将成为下一轮的左上角）
if text1[i - 1] == text2[j - 1]:
dp[j] = prev + 1 # 左上角 + 1
else:
dp[j] = max(dp[j], dp[j - 1]) # 上方 vs 左方
prev = temp # 更新左上角
return dp[n]思路三：递归 + 备忘录（自顶向下）
from functools import lru_cache
def longestCommonSubsequence(text1, text2):
@lru_cache(None)
def dfs(i, j):
if i == 0 or j == 0:
return 0
if text1[i - 1] == text2[j - 1]:
return dfs(i - 1, j - 1) + 1
else:
return max(dfs(i - 1, j), dfs(i, j - 1))
return dfs(len(text1), len(text2))易错点
- 索引偏移：
text1[i-1]对应dp[i]（前 i 个字符）。字符串索引和 dp 索引差 1。 - 遍历顺序不可颠倒：必须先处理 text1 再处理 text2（或反过来都可以，但要一致）。不能提前用 dp[i-1][j-1] 的末初始化值。
- 相等时取 dp[i-1][j-1] + 1：不是 dp[i-1][j] 或 dp[i][j-1] + 1。只有左上角状态才是两个字符串都退一个字符的 LCS。
- 不等时 max 的两个方向：max(dp[i-1][j], dp[i][j-1]) 分别对应”跳过 text1 的当前字符”和”跳过 text2 的当前字符”。
框架提炼
二维子序列 DP 模板：
def two_string_dp(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]) # 不等则跳过
return dp[m][n]这个模板适用于所有”两个序列/字符串比较”的问题，核心是决定”匹配”和”不匹配”时的状态转移。
关联题目
- 300-最长递增子序列 — 一维子序列 DP，可以转化为 LCS 求解（与排序去重后求 LCS）
- 72-编辑距离 — 相同二维 DP 结构，但转移更多（插入/删除/替换三种代价）
- 583-两个字符串的删除操作 — LCS 的变体，答案 = m + n - 2*LCS