1. 题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回
0
0
0 。
一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。
1.1 示例
- 输入：
text1 = "abcde" ，text2 = "ace" - 输出：
3
3
3
- 解释： 最长公共子序列是
"ace" ，它的长度为
3
3
3 。
-
示例
2
2
2： -
输入： text1 = "abc" ， text2 = "abc" -
输出：
3
3
3 -
解释： 最长公共子序列是 "abc" ，它的长度为
3
3
3 。 -
示例
3
3
3： -
输入： text1 = "abc" ， text2 = "def" -
输出：
0
0
0 -
解释： 两个字符串没有公共子序列，返回
0
0
0 。
1.2 说明
1.3 提示
1 <= text1.length, text2.length <= 1000text1 和 text2 仅由小写英文字符组成。
1.4 进阶
当 text1 和 text2 存在最长公共子序列时，你可以进一步输出该最长公共子序列么？
2. 解法一（动态规划）
2.1 分析
2.1.1 定义状态
dp[i][j] ：表示 text1 长度为 i 的前缀子序列和 text2 长度为 j 的前缀子序列二者最长公共子序列的长度。
这里我们引出了前缀子序列的概念，为便于后续讨论，下面给出前缀子序列的严格定义：
给定任意的序列
X
=
(
x
1
,
x
2
,
?
?
,
x
m
)
X=(x_1,x_2,\cdots,x_m)
X=(x1?,x2?,?,xm?) ，对于
i
=
0
,
1
,
?
?
,
m
i=0,1,\cdots,m
i=0,1,?,m ，则称
X
i
=
(
x
1
,
x
2
,
?
?
,
x
i
)
X_i=(x_1,x_2,\cdots,x_i)
Xi?=(x1?,x2?,?,xi?) 为
X
X
X 的第
i
i
i 个前缀子序列，显然
X
0
X_0
X0? 是一个空序列。
2.1.2 初始化状态
显然当 i 或 j 为
0
0
0 时 dp[i][j] 均为
0
0
0 。
2.1.3 状态转移
实际上，如果分别给定两个序列
X
=
(
x
1
,
x
2
,
?
?
,
x
m
)
X=(x_1,x_2,\cdots,x_m)
X=(x1?,x2?,?,xm?) 和
Y
=
(
y
1
,
y
2
,
?
?
,
y
n
)
Y=(y_1,y_2,\cdots,y_n)
Y=(y1?,y2?,?,yn?) ，且已知
Z
=
(
z
1
,
z
2
,
?
?
,
z
k
)
Z=(z_1,z_2,\cdots,z_k)
Z=(z1?,z2?,?,zk?) 为
X
X
X 和
Y
Y
Y 的任意一个最长公共子序列，则有如下性质：
- 如果
x
m
=
y
n
x_m = y_n
xm?=yn? ，则必然有
z
k
=
x
m
=
y
n
z_k = x_m = y_n
zk?=xm?=yn? 且
Z
k
?
1
Z_{k - 1}
Zk?1? 是
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
n
?
1
Y_{n - 1}
Yn?1? 的一个最长公共子序列；
- 如果
x
m
≠
y
n
x_m \ne y_n
xm??=yn? ，则由
z
k
≠
x
m
z_k \ne x_m
zk??=xm? 可推定
Z
Z
Z 是
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
Y
Y 的一个最长公共子序列；
- 如果
x
m
≠
y
n
x_m \ne y_n
xm??=yn? ，则由
z
k
≠
y
n
z_k \ne y_n
zk??=yn? 可推定
Z
Z
Z 是
X
X
X 和
Y
n
?
1
Y_{n - 1}
Yn?1? 的一个最长公共子序列。
下面给出对于上述性质的证明：
- 首先证明
z
k
=
x
m
z_k = x_m
zk?=xm? ，这里采用反证法，即先假设
z
k
≠
x
m
z_k \ne x_m
zk??=xm? ，则可以将
x
m
=
y
n
x_m = y_n
xm?=yn? 追加至
Z
Z
Z 的最后，此时得到了序列
X
X
X 和
Y
Y
Y 的一个长度为
k
+
1
k + 1
k+1 的公共子序列，这和
Z
Z
Z （长度为
k
k
k）是
X
X
X 和
Y
Y
Y 的最长公共子序列这一条件相矛盾，因此必有
z
k
=
x
m
=
y
n
z_k = x_m = y_n
zk?=xm?=yn? ；此外还需要证明
Z
k
?
1
Z_{k - 1}
Zk?1? 是
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
n
?
1
Y_{n - 1}
Yn?1? 的一个最长公共子序列，对此先假设
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
n
?
1
Y_{n - 1}
Yn?1? 有一个长度大于
k
?
1
k - 1
k?1 的公共子序列
W
W
W ，此时将
x
m
=
y
n
x_m = y_n
xm?=yn? 追加至
W
W
W 末尾就得到了
X
X
X 和
Y
Y
Y 的一个长度大于
k
k
k 的最长公共子序列，同样和条件矛盾，证毕；
- 如果
z
k
≠
x
m
z_k \ne x_m
zk??=xm? ，则显然
Z
Z
Z 是
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
Y
Y 的一个公共子序列，假设
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
Y
Y 有长度大于
k
k
k 的公共子序列
W
W
W ，则
W
W
W 必然也是
X
m
X_{m}
Xm? 和
Y
Y
Y 的公共子序列，这和
Z
Z
Z 为
X
X
X 和
Y
Y
Y 的最长公共子序列相矛盾，证毕；
- 证明方式同上。
实际上，根据上述性质可知：
- 当
x
m
=
y
n
x_m = y_n
xm?=yn? 时，通过在
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
n
?
1
Y_{n - 1}
Yn?1? 的最长公共子序列后面追加
x
m
=
y
n
x_m = y_n
xm?=yn? ，即得到
X
X
X 和
Y
Y
Y 的一个最长公共子序列；
- 当
x
m
≠
y
n
x_m \ne y_n
xm??=yn? 时，
X
m
?
1
X_{m - 1}
Xm?1? 和
Y
Y
Y 的最长公共子序列同
X
X
X 和
Y
n
?
1
Y_{n - 1}
Yn?1? 的最长公共子序列中更长的那个即为
X
X
X 和
Y
Y
Y 的一个最长公共子序列。
据此，我们可以写出下列状态转移方程：
d
p
[
i
,
j
]
=
{
0
i
=
0
?or?
j
=
0
d
p
[
i
?
1
,
j
?
1
]
i
,?
j
>
0
?and?
x
i
=
y
j
max
(
d
p
[
i
,
j
?
1
]
,
d
p
[
i
?
1
,
j
]
)
i
,?
j
>
0
?and?
x
i
≠
y
j
dp[i, j]= \begin{cases} 0& {i = 0} \text { or } {j = 0} \\ dp[i - 1, j - 1]& {i \text{, } j \gt 0} \text{ and } {x_i = y_j} \\ \text{max} (dp[i, j - 1], dp[i - 1, j])& {i \text{, } j \gt 0} \text{ and } {x_i \ne y_j} \end{cases}
dp[i,j]=??????0dp[i?1,j?1]max(dp[i,j?1],dp[i?1,j])?i=0?or?j=0i,?j>0?and?xi?=yj?i,?j>0?and?xi??=yj??
当 i > 0 且 j > 0 时：
- 如果
text1[i - 1] 和 text2[j - 1] 相同，则 dp[i][j] = dp[i - 1][j - 1] + 1 ； - 如果
text1[i - 1] 和 text2[j - 1] 不相同，则 dp[i][j] 取 dp[i - 1][j] 和 dp[i ][j - 1] 二者较大值。
2.1.4 返回结果
最终 dp[m][n] 即为所求的结果，其中
m
m
m 和
n
n
n 分别为 text1 和 text2 的长度。
2.2 解答
需要注意的是，下面代码并不是采用自顶向下的解法而是采用自下而上的解法：
class Solution:
def longest_common_subsequence(self, text1: str, text2: str) -> int:
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]
def main():
text1 = "abcde"
text2 = "ace"
sln = Solution()
print(sln.longest_common_subsequence(text1, text2))
if __name__ == '__main__':
main()
- 执行用时： 288 ms , 在所有 Python3 提交中击败了 90.36% 的用户；
- 内存消耗： 22.6 MB , 在所有 Python3 提交中击败了 50.58% 的用户。
2.3 复杂度
- 时间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中
m
m
m 和
n
n
n 分别是字符串
text1 和 text2 的长度。二维数组 dp 有
m
+
1
m+1
m+1 行和
n
+
1
n+1
n+1 列，需要对 dp 中的每个元素进行计算； - 空间复杂度：
O
(
m
n
)
O(mn)
O(mn)，其中
m
m
m 和
n
n
n 分别是字符串
text1 和 text2 的长度。创建了
m
+
1
m+1
m+1 行
n
+
1
n+1
n+1 列的二维数组 dp 。
3. 重建 LCS
from typing import List, Tuple
class Solution:
def __init__(self):
self._lcs = []
def _reconstruct_lcs(self, paths: List[List[str]], text1: str, i: int, j: int):
if i == 0 or j == 0:
return
if paths[i][j] == 'LEFT_UPWARD':
self._reconstruct_lcs(paths, text1, i - 1, j - 1)
self._lcs.append(text1[i - 1])
elif paths[i][j] == 'UPWARD':
self._reconstruct_lcs(paths, text1, i - 1, j)
else:
self._reconstruct_lcs(paths, text1, i, j - 1)
def calc_lcs(self, text1: str, text2: str) -> Tuple[int, List[List[str]]]:
m, n = len(text1), len(text2)
paths = [[''] * (n + 1) for _ in range(m + 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
paths[i][j] = 'LEFT_UPWARD'
elif dp[i - 1][j] >= dp[i][j - 1]:
dp[i][j] = dp[i - 1][j]
paths[i][j] = 'UPWARD'
else:
dp[i][j] = dp[i][j - 1]
paths[i][j] = 'LEFTWARD'
self._reconstruct_lcs(paths, text1, m, n)
return dp[m][n], self._lcs
def main():
text1 = "ABCBDAB"
text2 = "BDCABA"
sln = Solution()
length, lcs = sln.calc_lcs(text1, text2)
print(length, lcs)
if __name__ == '__main__':
main()
4. 参考资料
|