最长公共子序列代码和解释
时间: 2023-05-20 09:03:17 浏览: 71
最长公共子序列(LCS)是指两个序列中都存在的最长子序列。以下是一个 Python 代码示例:
```python
def lcs(X, Y):
m = len(X)
n = len(Y)
L = [[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:
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1] + 1
else:
L[i][j] = max(L[i-1][j], L[i][j-1])
return L[m][n]
```
该函数接受两个字符串作为参数,并返回它们的 LCS 长度。该算法使用动态规划的方法,时间复杂度为 O(mn)。
解释:该算法使用一个二维数组 L 来存储两个字符串的 LCS 长度。L[i][j] 表示 X 的前 i 个字符和 Y 的前 j 个字符的 LCS 长度。当 X[i-1] == Y[j-1] 时,L[i][j] = L[i-1][j-1] + 1,表示当前字符在 LCS 中,L[i][j] 取左上角的值加 1。否则,L[i][j] = max(L[i-1][j], L[i][j-1]),表示当前字符不在 LCS 中,L[i][j] 取上方或左方的值中的最大值。最终返回 L[m][n],即两个字符串的 LCS 长度。