Adrian Wang's blog

一个完全由AI生成，但是内容高质量的Blog

LeetCode 1143 - 最长公共子序列 (Longest Common Subsequence)

Posted on Edited on In , ,
Symbols count in article: 3.8k Reading time ≈ 3 mins.
LeetCode 1143 最长公共子序列问题详解，使用动态规划思路解决，并提供 Go 语言的实现代码和复杂度分析。

问题描述

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

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

例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= text1.length, text2.length <= 1000
  • text1 和 text2 仅由小写英文字符组成。

解题思路

这道题是典型的动态规划问题。动态规划的核心思想是将一个大问题分解为若干个子问题，通过解决这些子问题，并存储它们的结果，来最终解决大问题。

1. 定义 DP 数组的含义

我们创建一个二维数组 dp，其中 dp[i][j] 用来存储字符串 text1 的前 i 个字符（即子串 text1[0...i-1]）与字符串 text2 的前 j 个字符（即子串 text2[0...j-1]）的最长公共子序列的长度。

例如，如果 text1 = "abc"，text2 = "axc"：

  • dp[1][1] 表示 text1 的前 1 个字符 “a” 和 text2 的前 1 个字符 “a” 的最长公共子序列长度。
  • dp[3][2] 表示 text1 的前 3 个字符 “abc” 和 text2 的前 2 个字符 “ax” 的最长公共子序列长度。

2. 状态转移方程

当我们计算 dp[i][j] 时，我们需要观察 text1 的第 i 个字符（即 text1[i-1]）和 text2 的第 j 个字符（即 text2[j-1]）：

  • 情况一：text1[i-1] == text2[j-1]
    如果这两个字符相等，那么这个相等的字符 text1[i-1] (或 text2[j-1]) 必然可以作为 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的最后一个字符。
    因此，dp[i][j] 就等于 text1[0...i-2] 和 text2[0...j-2] 的最长公共子序列的长度，再加上这个共同的字符（长度加 1）。
    所以，dp[i][j] = dp[i-1][j-1] + 1。

  • 情况二：text1[i-1] != text2[j-1]
    如果这两个字符不相等，那么 text1[i-1] 和 text2[j-1] 中至少有一个字符不能包含在 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列中。
    这时，dp[i][j] 的值取决于以下两种可能中较大的那个：

    1. 不考虑 text1[i-1]，即 text1[0...i-2] 和 text2[0...j-1] 的最长公共子序列长度，也就是 dp[i-1][j]。
    2. 不考虑 text2[j-1]，即 text1[0...i-1] 和 text2[0...j-2] 的最长公共子序列长度，也就是 dp[i][j-1]。
      所以，dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

3. 初始化 DP 数组（边界条件）

  • dp[0][j]：表示 text1 为空字符串（长度为 0）与 text2 的前 j 个字符的最长公共子序列。空字符串与任何字符串的公共子序列长度都是 0。所以 dp[0][j] = 0 对所有 j 成立。
  • dp[i][0]：表示 text1 的前 i 个字符与 text2 为空字符串（长度为 0）的最长公共子序列。同理，长度也是 0。所以 dp[i][0] = 0 对所有 i 成立。
  • 因此，dp[0][0] (空串与空串的 LCS) 自然也是 0。
    在 Go 语言中，make 创建的 int 类型切片默认值为 0，所以这部分初始化可以省略显式赋值。

4. 填表顺序与最终结果

我们从 dp[1][1] 开始，逐行逐列地填充 dp 表，直到 dp[n][m]，其中 n 是 text1 的长度，m 是 text2 的长度。
最终 dp[n][m] 就是我们要求的 text1 和 text2 整个字符串的最长公共子序列的长度。

举例手动推演：

假设 text1 = "ab"，text2 = "axb"。
n = 2, m = 3。
DP 表大小为 (2+1) x (3+1) = 3x4.

初始化：
dp 表所有元素为 0。

1
2
3
4
5
      ""  a   x   b   (text2)
""    0   0   0   0
a     0
b     0
(text1)

开始填充：

  • i=1, j=1: text1[0] (‘a’) == text2[0] (‘a’)
    dp[1][1] = dp[0][0] + 1 = 0 + 1 = 1
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1
b     0
  • i=1, j=2: text1[0] (‘a’) != text2[1] (‘x’)
    dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1   1
b     0
  • i=1, j=3: text1[0] (‘a’) != text2[2] (‘b’)
    dp[1][3] = max(dp[0][3], dp[1][2]) = max(0, 1) = 1
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1   1   1
b     0
  • i=2, j=1: text1[1] (‘b’) != text2[0] (‘a’)
    dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1   1   1
b     0   1
  • i=2, j=2: text1[1] (‘b’) != text2[1] (‘x’)
    dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1   1   1
b     0   1   1
  • i=2, j=3: text1[1] (‘b’) == text2[2] (‘b’)
    dp[2][3] = dp[1][2] + 1 = 1 + 1 = 2
1
2
3
4
      ""  a   x   b
""    0   0   0   0
a     0   1   1   1
b     0   1   1   2

最终结果 dp[2][3] = 2。最长公共子序列是 “ab”.

最终的结果是 dp[n][m]，其中 n 是 text1 的长度，m 是 text2 的长度。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
// filepath: /Users/adrianwang/.leetcode/1143.最长公共子序列.go
package main

/*
 * @lc app=leetcode.cn id=1143 lang=golang
 *
 * [1143] 最长公共子序列
 */

// @lc code=start
func longestCommonSubsequence(text1 string, text2 string) int {
	n, m := len(text1), len(text2)

	// dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列长度
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, m+1)
	}

	// base case: dp[0][...] 和 dp[...][0] 均为 0，Go 语言中默认初始化为 0

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			if text1[i-1] == text2[j-1] {
				// 当前字符匹配，LCS 长度加 1
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				// 当前字符不匹配，取两种情况的最大值
				// 1. text1[0...i-2] 和 text2[0...j-1] 的 LCS
				// 2. text1[0...i-1] 和 text2[0...j-2] 的 LCS
				dp[i][j] = max(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	return dp[n][m]
}

// @lc code=end

// max 函数辅助
// func max(a, b int) int {
// 	if a > b {
// 		return a
// 	}
// 	return b
// }

注意： 上述代码中 max 函数在 LeetCode 环境中通常是内置的或可以直接使用，如果本地运行需要自行定义。在 1143.最长公共子序列.go 文件中，max 函数是存在的。

复杂度分析

  • 时间复杂度： O(n*m)，其中 n 是 text1 的长度，m 是 text2 的长度。我们需要填充一个 n*m 大小的 DP 表。
  • 空间复杂度： O(n*m)，用于存储 DP 表。

关键收获

  • 动态规划是解决最长公共子序列问题的经典方法。
  • 正确定义 DP 状态 dp[i][j] 的含义至关重要，通常表示考虑子问题 text1[0...i-1] 和 text2[0...j-1].
  • 仔细推导状态转移方程，考虑字符匹配和不匹配两种情况。
  • 注意 DP 表的初始化和边界条件。