我来给你讲解 LeetCode 第 1143 题「最长公共子序列」。

题目描述

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

子序列的定义：一个字符串的子序列是通过删除原字符串某些字符（也可以不删除）而不改变剩余字符相对位置形成的新字符串。例如，"ace" 是 "abcde" 的子序列。

示例 1：

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

示例 2：

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

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0。

解题思路详解

第一步：理解问题本质

最长公共子序列（LCS）问题是经典的动态规划问题。我们需要找到两个字符串中顺序相同但可以不连续的最长公共部分。

关键点：

• 子序列不要求连续，只要求相对顺序一致
• 我们要找的是最长的那一个公共子序列

第二步：暴力解法分析

最直接的思路是枚举所有可能性：

• 枚举 text1 的所有子序列（2^m 个）
• 枚举 text2 的所有子序列（2^n 个）
• 检查哪些子序列相同，找出最长的

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

第三步：动态规划思路

我们使用二维 DP 表格来记录子问题的解：

定义状态：

• dp[i][j] 表示 text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度
• 注意：i 和 j 表示前几个字符，不是下标（这样处理边界更方便）

状态转移方程：

1. 如果 text1[i-1] == text2[j-1]（当前字符相同）：

   • 这个字符一定在公共子序列中
   • dp[i][j] = dp[i-1][j-1] + 1

2. 如果 text1[i-1] != text2[j-1]（当前字符不同）：

   • 最长公共子序列可能来自两种情况：
     • 排除 text1 的当前字符：dp[i-1][j]
     • 排除 text2 的当前字符：dp[i][j-1]
   • dp[i][j] = max(dp[i-1][j], dp[i][j-1])

基础情况：

• 如果某个字符串为空，LCS 长度为 0
• dp[0][j] = 0（text1 为空）
• dp[i][0] = 0（text2 为空）

第四步：具体示例演示

以 text1 = "abcde", text2 = "ace" 为例：

初始化 DP 表（多出一行一列用于基础情况）：

    "" a c e
""   0 0 0 0
a    0
b    0
c    0
d    0
e    0

逐步填充：

1. i=1, j=1: text1[0]='a' = text2[0]='a' → dp[1][1] = dp[0][0] + 1 = 1
2. i=1, j=2: 'a' ≠ 'c' → dp[1][2] = max(dp[0][2], dp[1][1]) = max(0,1) = 1
3. i=1, j=3: 'a' ≠ 'e' → dp[1][3] = max(dp[0][3], dp[1][2]) = max(0,1) = 1

继续填充完整表格：

    "" 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

最终结果：dp[5][3] = 3

第五步：代码实现

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    # 创建 (m+1) x (n+1) 的二维数组，初始化为0
    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]:
                # 字符匹配，长度加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)，需要填充 m × n 的 DP 表
• 空间复杂度：O(m × n)，DP 表的大小

第七步：空间优化（进阶）

我们可以将空间复杂度优化到 O(min(m, n))：

def longestCommonSubsequence(text1: str, text2: str) -> int:
    # 让text2是较短的字符串以节省空间
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    
    m, n = len(text1), len(text2)
    # 只保留两行：当前行和上一行
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        # 交换引用，准备下一轮
        prev, curr = curr, prev
    
    return prev[n]

第八步：重构实际序列（扩展）

如果需要输出最长公共子序列本身，而不仅仅是长度：

def longestCommonSubsequenceWithSequence(text1: str, text2: str):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充DP表
    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])
    
    # 反向追踪构造序列
    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))

这个算法是很多字符串处理问题的基础，也是动态规划的经典范例。