LeetCode 1143. Longest Common Subsequence

题目链接

题意

找出两个串的最长公共前缀

思路

很常用的dp套路,$dp[i][j]$表示$s_1$的$1-i$和$s_2$的$1-j$的最长公共前缀的长度,转移方程如下:

$dp[i][j] = dp[i-1][j-1]$ if $s_1[i] == s_2[j]$
$dp[i][j] = \max(dp[i-1][j],dp[i][j-1])$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n, m = len(text1), len(text2)
dp = [[0]*(m + 1) for i in range(n + 1)]

for i in range(n):
for j in range(m):
if text1[i] == text2[j]:
dp[i + 1][j + 1] = dp[i][j] + 1
else:
dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
return dp[n][m]

二维降为一维

可以发现上述方法时间复杂度为$O(nm)$,空间复杂度为$O(nm)$。
下面将空间复杂度降为$O(\min(n,m))$
可以发现对于每一个状态$dp[i][j]$,只需要$dp[i-1][j],dp[i-1][j-1],dp[i][j-1]$这三个前面的状态,所以dp数组的大小可以只用$dp[2][m]$即可。再进一步,对于$dp[j]$来说,每一个$i$,只需记录其对角的值$dp[i-1][j-1]$,此时对应的$dp[j],dp[j-1]$分别就是$dp[i-1][j],dp[i][j-1]$(因为$dp[j]$后于$dp[j-1]$更新)

1
2
3
4
5
6
7
8
9
10
11
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
n, m = len(text1), len(text2)
dp = [0]*(m + 1)
for i in range(n):
prediag = 0
for j in range(m):
ans = dp[j + 1]
dp[j + 1] = prediag + 1 if text1[i] == text2[j] else max(dp[j], dp[j + 1])
prediag = ans
return dp[-1]


-------------本文结束感谢您的阅读-------------


本文标题:LeetCode 1143. Longest Common Subsequence

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2020年02月06日 - 10:02

最后更新:2020年02月06日 - 11:02

原始链接:https://statusrank.xyz/articles/b4f04603.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!

相关文章: