【刷题】LCS算法-最长公共子序列

本文主要是介绍【刷题】LCS算法-最长公共子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求两个字符串的公共最长序列。

例如,

• 输入：‘acbde’ , ‘cfebd’
• 输出：3 (最长的公共子序列为’cbd’)

动态规划：

• i == 0 or j == 0, dp[i][j] = 0
• A[i] == B[j], dp[i][j] = dp[i−1][j−1]+1
• A[i] != B[j], dp[i][j] = max(dp[i−1][j], dp[i][j−1])

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:m = len(A)n = len(B)dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]for i in range(n + 1):for j in range(m + 1):if i == 0 or j == 0:dp[i][j] = 0elif B[i - 1] == A[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[-1][-1]

特别强调：
注意区分这两个概念：

1. 最长公共子序列
2. 最长公共子串

最长公共子串要求的是连续，而最长公共子序列不一定连续；
所以例子中的两个字符串’acbde’，‘cfebd’：

1. 输出 3 ‘cbd’
2. 输出 2 ‘bd’

动态规划的条件差不多：

• i == 0 or j == 0, dp[i][j] = 0
• A[i] == B[j], dp[i][j] = dp[i−1][j−1]+1
• 最后输出要输出最大值

class Solution:def findLength(self, A: List[int], B: List[int]) -> int:m = len(A)n = len(B)dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]for i in range(n + 1):for j in range(m + 1):if i == 0 or j == 0:dp[i][j] = 0elif B[i - 1] == A[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1return max(max(row) for row in dp)

这篇关于【刷题】LCS算法-最长公共子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---