好的，我们接下来讲解 LeetCode 第 1143 题「最长公共子序列」。

1. 题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的 最长公共子序列 的长度。如果不存在公共子序列，返回 0。

一个字符串的 子序列 是指这样一个新字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如：

• "ace" 是 "abcde" 的子序列。
• "abc" 是 "abc" 的子序列。
• "abc" 不是 "def" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace"，它的长度为 3。

示例 2：

输入：text1 = "abc", text2 = "abc"
输出：3

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0

2. 问题分析与思路

关键点理解

• 子序列 不是子串，不要求连续，但必须保持相对顺序。
• 我们需要找到两个字符串中都出现的最长子序列的长度。

初步思考：暴力解法

一个最直接的想法是：

1. 生成 text1 的所有子序列（共有 2^m 个，m 是 text1 的长度）。
2. 生成 text2 的所有子序列（共有 2^n 个）。
3. 找出最长的公共子序列。

但这样时间复杂度是 O(2^(m+n))，完全不可行。

引入动态规划（DP）

这类“两个序列”的匹配问题，常用 二维动态规划 解决。

定义状态：

• 设 dp[i][j] 表示 text1 的前 i 个字符（即 text1[0..i-1]）和 text2 的前 j 个字符（即 text2[0..j-1]）的最长公共子序列的长度。
• 注意：i 和 j 可以取 0，表示空字符串。

状态转移方程：
我们需要考虑 text1 的第 i 个字符（即 text1[i-1]）和 text2 的第 j 个字符（即 text2[j-1]）：

1. 如果 text1[i-1] == text2[j-1]：

   • 当前两个字符相等，它们一定在最长公共子序列中。
   • 所以 dp[i][j] = dp[i-1][j-1] + 1。

2. 如果 text1[i-1] != text2[j-1]：

   • 当前两个字符不相等，它们不可能同时出现在公共子序列中。
   • 那么最长公共子序列可能来自：
     • text1 的前 i-1 个字符和 text2 的前 j 个字符（即 dp[i-1][j]）。
     • text1 的前 i 个字符和 text2 的前 j-1 个字符（即 dp[i][j-1]）。
   • 取最大值：dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

初始条件：

• 当 i = 0 时，text1 是空字符串，与任何 text2 的前 j 个字符的公共子序列长度为 0，所以 dp[0][j] = 0。
• 当 j = 0 时，同理 dp[i][0] = 0。

最终答案：

• dp[m][n]，其中 m = len(text1)，n = len(text2)。

3. 详细步骤推导（以示例 1 为例）

text1 = "abcde", text2 = "ace"

初始化 dp 表（大小为 (m+1) x (n+1)，初始全 0）：

逐行填充：

i=1 (text1[0] = 'a')：

• j=1 (text2[0] = 'a')：相等 → dp[1][1] = dp[0][0] + 1 = 0+1 = 1
• j=2 (text2[1] = 'c')：不等 → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0,1) = 1
• j=3 (text2[2] = 'e')：不等 → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0,1) = 1

i=2 (text1[1] = 'b')：

• j=1：不等 → dp[2][1] = max(dp[1][1], dp[2][0]) = max(1,0) = 1
• j=2：不等 → dp[2][2] = max(dp[1][2], dp[2][1]) = max(1,1) = 1
• j=3：不等 → dp[2][3] = max(dp[1][3], dp[2][2]) = max(1,1) = 1

i=3 (text1[2] = 'c')：

• j=1：不等 → dp[3][1] = max(dp[2][1], dp[3][0]) = max(1,0) = 1
• j=2：相等 → dp[3][2] = dp[2][1] + 1 = 1+1 = 2
• j=3：不等 → dp[3][3] = max(dp[2][3], dp[3][2]) = max(1,2) = 2

i=4 (text1[3] = 'd')：

• j=1：不等 → dp[4][1] = max(dp[3][1], dp[4][0]) = max(1,0) = 1
• j=2：不等 → dp[4][2] = max(dp[3][2], dp[4][1]) = max(2,1) = 2
• j=3：不等 → dp[4][3] = max(dp[3][3], dp[4][2]) = max(2,2) = 2

i=5 (text1[4] = 'e')：

• j=1：不等 → dp[5][1] = max(dp[4][1], dp[5][0]) = max(1,0) = 1
• j=2：不等 → dp[5][2] = max(dp[4][2], dp[5][1]) = max(2,1) = 2
• j=3：相等 → dp[5][3] = dp[4][2] + 1 = 2+1 = 3

最终 dp[5][3] = 3，即最长公共子序列长度为 3。

4. 代码实现（Python）

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # 初始化 dp 表，大小为 (m+1) x (n+1)
    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]

复杂度分析：

• 时间复杂度：O(m * n)，需要填充整个 dp 表。
• 空间复杂度：O(m * n)，即 dp 表的大小。可以优化到 O(min(m, n))（使用滚动数组）。

5. 总结与扩展

• 核心思想：通过二维 DP 记录两个字符串前缀的最长公共子序列长度，利用字符相等或不等的情况进行状态转移。
• 关键点：理解 dp[i][j] 的定义，以及当字符不相等时为什么要取 max(dp[i-1][j], dp[i][j-1])（因为当前字符不能同时出现在公共子序列中，所以只能忽略其中一个字符继续找）。
• 类似问题：最长公共子串（要求连续）、编辑距离等。

这样，我们就完成了「最长公共子序列」的详细讲解。