1143. 最长公共子序列
class LongestCommonSubsequence2:
"""
1143. 最长公共子序列
https://leetcode.cn/problems/longest-common-subsequence/
"""
def solution(self, text1: str, text2: str) -> int:
"""
递归解法 + 备忘录
自顶向下
:param text1:
:param text2:
:return:
"""
m, n = len(text1), len(text2)
self.memo = [[-1 for _ in range(n)] for _ in range(m)]
return self.dp(text1, 0, text2, 0)
def dp(self, text1, i, text2, j):
"""
计算text1[i..] 和 text2[j..]的子序列长度
:param text1:
:param i:
:param text2:
:param j:
:return:
"""
# base case
if i == len(text1) or j == len(text2):
return 0
# 备忘录
if self.memo[i][j] != -1:
return self.memo[i][j]
if text1[i] == text2[j]:
self.memo[i][j] = 1 + self.dp(text1, i+1, text2, j+1)
else:
self.memo[i][j] = max(self.dp(text1, i + 1, text2, j),
self.dp(text1, i, text2, j + 1))
return self.memo[i][j]
@classmethod
def solution2(cls, text1: str, text2: str) -> int:
"""
自底向上
迭代 动规
:param text1:
:param text2:
:return:
"""
m, n = len(text1), len(text2)
# dp[m][n] 表示 text1[0..m-1][0..n-1]的lcs
dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
# base case
# dp[0][...] dp[...][0] = 0
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
return dp[m][n]
