求最长公共子序列的长度

在本教程中，我们将首先简要解释什么是子序列和最长公共子序列，然后再直接深入代码。在代码部分，我们将学习如何使用递归和动态规划来发现最长公共子序列的长度。

让我们立即开始吧。

什么是子序列？

字符串子序列是通过从前一个字符串中删除部分字符而创建的新字符串，同时保持字符的相对位置不变。

例如 –
原始字符串 =“ABCDVWXYZ”
有效子序列 =“ACDW”、“BYZ”、“ACWXYZ”
无效子序列 =“VAYZ”、“DYAZ”、“XBACW”

什么是最长公共子序列（LCS）？

给定一组序列，最大的公共子序列挑战是识别所有序列共享的最长子序列。最长公共子序列问题的答案并不总是唯一的。可能存在许多具有最长可行长度的公共子序列。

例如 –
序列 1 = “BAHJDGSTAH”
序列 2 = “HDSABTGHD”
序列 3 = “ABTH”
LCS 长度 = 3
LCS = “ATH”、“BTH”

方法一：递归

我们从末尾开始以递归方式比较字符串，一次一个字符。设 LCS 为确定两个字符串共享的最长子序列长度的函数。

有两种可能的情况：

字符是相同的 – 将 1 添加到 LCS 并通过消除最后一个字符来使用更新的字符串递归执行该过程 – LCS (str1, str2, m-1, n-1)。
字符是不同的 – 不超过（递归调用字符串 1 并删除最后一个字符，递归调用字符串 2 并删除最后一个字符）。

def lcs(str1, str2, m, n):
    if m==0 or n==0:
        return 0
    elif str1[m-1] == str2[n-1]: 
        return 1+lcs(str1, str2, m-1, n-1) 
    else: 
        return max(lcs(str1, str2, m-1, n),lcs(str1, str2, m,n-1))
str1 = input("Enter first string: ")
str2 = input("Enter second string: ")
lcs_length = lcs(str1, str2, len(str1), len(str2))
print("length of LCS is : {}".format(lcs_length))

Enter first string: BAHJDGSTAH
Enter second string: BAHJDGSTAH
length of LCS is : 5

方法2：动态规划方法

该技术采用自下而上的策略。子问题的解决方案保存在矩阵中以供将来使用。这称为记忆化。如果两个字符串的长度分别为m和n，则动态规划的时间复杂度为O(mn)，大大小于递归的时间复杂度。矩阵的最后一项表示 LCS 的长度。

def lcs(str1 , str2):
    m = len(str1)
    n = len(str2)
    matrix = [[0]*(n+1) for i in range(m+1)] 
    for i in range(m+1):
        for j in range(n+1):
            if i==0 or j==0:
                matrix[i][j] = 0
            elif str1[i-1] == str2[j-1]:
                matrix[i][j] = 1 + matrix[i-1][j-1]
            else:
                matrix[i][j] = max(matrix[i-1][j] , matrix[i][j-1])
    return matrix[-1][-1]
str1 = input("Enter first string: ")
str2 = input("Enter second string: ")
lcs_length = lcs(str1, str2)
print("Length of LCS is : {}".format(lcs_length))

Enter first string: BAHJDGSTAH
Enter second string: BAHJDGSTAH
length of LCS is : 5

结论

恭喜！您刚刚学习了如何显示最长公共子序列的长度。

喜欢该教程吗？无论如何，我建议您查看下面提到的教程：

感谢您抽出宝贵时间！希望你学到新东西！😄