快捷導(dǎo)航

Python 中最長(zhǎng)公共子序列的長(zhǎng)度

更新時(shí)間：2023年06月20日 11:13:28 作者：跡憶客

子序列是在不改變剩余字符的順序的情況下，在刪除一些字符或不刪除任何字符后從給定序列獲得的序列，這篇文章主要介紹了Python 中的最長(zhǎng)公共子序列,需要的朋友可以參考下

使用 Naive 方法在 Python 中查找最長(zhǎng)公共子序列

假設(shè)我們有兩個(gè)序列：S1 和 S2，其中：

S1 = QEREW
S2 = QWRE

這里，常見的子序列是 QE、QW、QR、QRE 和 RE。其中最長(zhǎng)的公共子序列是QRE，長(zhǎng)度為3。

現(xiàn)在，讓我們看看打印最長(zhǎng)公共子序列長(zhǎng)度的 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 問(wèn)題。它檢查給定序列的所有可能子序列并找到最長(zhǎng)的公共子序列。

使用動(dòng)態(tài)規(guī)劃在 Python 中查找最長(zhǎng)公共子序列

動(dòng)態(tài)規(guī)劃是普通遞歸方法的優(yōu)化。正如我們所看到的，遞歸方法中存在重疊的子問(wèn)題，具有許多重復(fù)的函數(shù)調(diào)用。

動(dòng)態(tài)方法將每個(gè)函數(shù)調(diào)用的結(jié)果保存在一個(gè)數(shù)組中，以便在需要時(shí)使用。結(jié)果，它減少了函數(shù)調(diào)用的次數(shù)。

代碼：

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))

輸出: