迹忆客 专注技术分享

子序列是在不改变剩余字符的顺序的情况下，在删除一些字符或不删除任何字符后从给定序列获得的序列。 最长公共子序列是指所有给定序列共有的最长子序列。

本篇文章讲介绍在 Python 中查找两个序列之间最长公共子序列的长度。

使用 Naive 方法在 Python 中查找最长公共子序列

假设我们有两个序列：S1 和 S2，其中：

S1 = QEREW

S2 = QWRE

这里，常见的子序列是 QE、QW、QR、QRE 和 RE。 其中最长的公共子序列是QRE，长度为3。

现在，让我们看看打印最长公共子序列长度的 Python 解决方案。

代码：

def LCS(S1, S2, x, y):

    if x == 0 or y == 0:
        return 0

    if S1[x - 1] == S2[y - 1]:
        return LCS(S1, S2, x - 1, y - 1) + 1

    return max(LCS(S1, S2, x, y - 1), LCS(S1, S2, x- 1, y))
S1 = "QEREW"
S2 = "QWRE"
x = len(S1)
y = len(S2)
print ("Length of LCS is", LCS(S1, S2, x, y))

输出:

Length of LCS is 3

这种方法是用递归方法解决 Python 中的 LCS 问题。 它检查给定序列的所有可能子序列并找到最长的公共子序列。

使用动态规划在 Python 中查找最长公共子序列

动态规划是普通递归方法的优化。 正如我们所看到的，递归方法中存在重叠的子问题，具有许多重复的函数调用。

动态方法将每个函数调用的结果保存在一个数组中，以便在需要时使用。 结果，它减少了函数调用的次数。

代码：

def LCS(S1, S2, m, n):
    R = [[None]*(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:
                R[i][j] = 0
            elif S1[i-1] == S2[j-1]:
                R[i][j] = R[i-1][j-1] + 1
            else:
                R[i][j] = max(R[i-1][j], R[i][j-1])

    return R[m][n]

S1 = "QEREW"
S2 = "QWRE"
m = len(S1)
n = len(S2)
print("Length of LCS is",LCS(S1, S2, m, n))

输出:

Length of LCS is 3

这种方法更快、更有效，因为它具有 O(mn) 的时间复杂度。