longestCommonSubsequence

计算两个字符串的最长公共子序列(Longest Common Subsequence - LCS),使用动态规划算法实现。

输入字符串

字符串 1

字符串 2

执行过程

步骤 1 / 84

初始化DP表，第0行和第0列均为0

		A	E	D	F	H	R
	0	0	0	0	0	0	0
A	0	0	0	0	0	0	0
B	0	0	0	0	0	0	0
C	0	0	0	0	0	0	0
D	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
H	0	0	0	0	0	0	0

速度:慢速正常快速超快

正在比较

当前单元格

来源单元格

回溯路径

算法说明

最长公共子序列(LCS)使用动态规划求解。构建DP表后通过回溯得到实际序列。时间复杂度O(m×n)，空间复杂度O(m×n)。

函数签名

function longestCommonSubsequence(
  str1: string,
  str2: string,
  includeDpTable?: boolean
): LCSResult

interface LCSResult {
  length: number
  sequence: string
  dpTable?: number[][]
}

参数

参数名	类型	必填	说明
str1	string	是	第一个字符串
str2	string	是	第二个字符串
includeDpTable	boolean	否	是否在结果中包含DP表(用于调试),默认false

返回值

类型	说明
LCSResult	LCS结果对象

LCSResult 结构:

属性	类型	说明
length	number	最长公共子序列的长度
sequence	string	最长公共子序列字符串
dpTable	number[][]	DP表(可选,仅当includeDpTable为true时)

工作原理

1. 创建DP表: 创建一个 (m+1) × (n+1) 的二维数组,其中 m 和 n 分别是两个字符串的长度
2. 填充DP表:
   • 如果 str1[i-1] === str2[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
   • 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
3. 回溯构建序列: 从 dp[m][n] 开始回溯,根据状态转移方向构建LCS字符串
4. 返回结果: 返回LCS长度和序列字符串

时间复杂度: O(m×n),其中 m 和 n 是两个字符串的长度
空间复杂度: O(m×n)