专业网站设计速寻亿企邦,湖北做网站教程哪家好,asp网站栏目修改,如何挑选网站主机题目 一个字符串的子序列是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff08;也可以不删除任何字符#xff09;后组成的新字符串。比如#xff1a;ace 是 abcde 的子序列#xff0c;但 它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。比如ace 是 abcde 的子序列但 aec 不是 abcde 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。 现给定两个字符串 text1 和 text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 返回0。 备注text1 和 text2 仅由小写英文字符组成。 示例 1
输入text1 abcde, text2 ace
输出3
解释最长公共子序列是ace 它的长度为3。 示例 2
输入text1 abc, text2 abc
输出3
解释最长公共子序列是abc它的长度为3。 示例 3
输入text1 abc, text2 def
输出0
解释两个字符串没有公共子序列返回0。 递归法 最长公共子序列英文全称为Longest Common Subsequence一般缩写为LCS。 递归法求解LCS的基本思想是将大问题分解为小问题通过比较两个字符串的末尾字符是否相等来决定如何递归地解决问题。如果两个字符串的末尾字符相等那么这个字符必定属于LCS的一部分。如果不相等就需要分别去掉一个字符串的末尾字符递归地求解子问题。使用递归法求解本题的主要步骤如下。 1、如果任意一个字符串为空那么最长公共子序列的长度为0。 2、如果 text1 的最后一个字符和 text2 的最后一个字符相同那么我们递归地求解 text1[:-1] 和 text2[:-1] 的LCS长度并在结果上加1。 3、如果 text1 的最后一个字符和 text2 的最后一个字符不同那么我们递归地求解 text1[:-1] 和 text2 的LCS长度以及 text1 和 text2[:-1] 的LCS长度取两者中较大的一个。 根据上面的算法步骤我们可以得出下面的示例代码。
def lcs_by_recursion(text1, text2):def lcs_helper(t1, t2):if not t1 or not t2:return 0if t1[-1] t2[-1]:# 末尾字符相同return lcs_helper(t1[:-1], t2[:-1]) 1else: # 末尾字符不同return max(lcs_helper(t1[:-1], t2), lcs_helper(t1, t2[:-1]))return lcs_helper(text1, text2)print(lcs_by_recursion(abcde, ace))
print(lcs_by_recursion(abc, abc))
print(lcs_by_recursion(abc, def)) 动态规划法 动态规划法通过构建一个二维数组来存储子问题的解以避免重复计算。对于任意两个字符串的前缀其最长公共子序列的长度取决于前一个字符是否相等如果相等则长度加1如果不等则取两者可能的最长公共子序列的最大值。使用动态规划法求解本题的主要步骤如下。 1、初始化。定义一个二维数组 dp大小为 (len(text1) 1) x (len(text2) 1)。初始状态下dp[0][j] 0dp[i][0] 0。这是因为空字符串与任何字符串的最长公共子序列长度都为0。 2、状态转移方程。遍历 text1 和 text2 的每个字符对于 text1 中的第 i 个字符和 text2 中的第 j 个字符进行以下操作。 1如果 text1[i-1] 等于 text2[j-1]则 dp[i][j] dp[i-1][j-1] 1。 2如果 text1[i-1] 不等于 text2[j-1]则 dp[i][j] max(dp[i-1][j], dp[i][j-1])。 3、边界条件。当任一字符串为空时最长公共子序列长度为0这已经在初始化时处理。 4、获取结果。最终答案位于dp数组的右下角即dp[len(text1)][len(text2)]。
def lcs_by_dp(text1: str, text2: str) - int:m, n len(text1), len(text2)# 初始化DP表dp [[0] * (n 1) for _ in range(m 1)]# 填充DP表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] 1else:dp[i][j] max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]print(lcs_by_dp(abcde, ace))
print(lcs_by_dp(abc, abc))
print(lcs_by_dp(abc, def)) 总结 虽然递归法直观且易于理解但它存在严重的重复计算问题导致时间复杂度为指数级效率极低。因此在实际应用中递归法通常被动态规划法所替代。动态规划法可以避免重复计算将时间复杂度降低至O(m*n)其中m和n分别是两个字符串的长度。
