最长公共子序列你学会了吗
最长公共子序列
问题描述
给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1″。目前给出的数据，仅仅会存在一个最长的公共子序列。
示例：
输入：”abcde”，”ace”
输出：”ace”
分析问题
首先，我们先来看一下什么是子序列。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace”是“abcde”的子序列，但是“aec”不是“abcde”的子序列。这个问题和求最长公共子串类似，我们也可以采用动态规划的方法来求解。
我们假设str1[0,i-1]和str2[0,j-1]的最长公共子序列为dp[i-1] [j-1]，那么str1[0,i]和str2[0,j]的最长公共子序列等于多少呢？这主要取决于字符str1[i]和str2[j]是否相等，如果相等，则最长公共子序列会加1，即dp[i] [j] = dp[i-1] [j-1] + 1。如果不相等，则dp[i] [j] = max(dp[i-1] [j],dp[i] [j-1])。有了动态转移方程，我们只需要遍历字符串，逐步填写状态转移矩阵就好了。
下面我们来看一下代码如何实现。
def longestCommonSubsequence(str1,str2):
n=len(str1)
m=len(str2)
dp=[[0 for _ in range(n)] for _ in range(m)]
#处理边界条件
if str1[0]==str2[0]:
dp[0][0] = 1
for i in range(n):
if(str2[0]==str1[i]):
dp[0][i]=1
else:
dp[0][i]=dp[0][i-1]
for j in range(m):
if(str1[0]==str2[j]):
dp[j][0] = 1
else:
dp[j][0] = dp[j-1][0]
for i in range(1, m):
for j in range(1, n):
if str2[i]==str1[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m-1][n-1]
由于题目要求是输出具体的子序列，所以我们还需要根据状态转移矩阵逆推回去。
通过状态转移方程，我们可以知道dp[i] [j]要么从dp[i-1] [j-1] +1 求得，要么通过dp[i] [j-1] 和 dp[i-1] [j]的最大值得到，所以我们可以从dp[m-1] [n-1] 倒推出str1和str2的最大公共子序列。如下图所示。
我们来看一下完整的代码实现。
def LCS(self , str1 , str2 ):
n=len(str1)
m=len(str2)
if n==0 or m==0:
return -1
dp=[[0 for _ in range(n)] for _ in range(m)]
#处理边界条件
if str1[0]==str2[0]:
dp[0][0] = 1
for i in range(n):
if(str2[0]==str1[i]):
dp[0][i]=1
else:
dp[0][i]=dp[0][i-1]
for j in range(m):
if(str1[0]==str2[j]):
dp[j][0] = 1
else:
dp[j][0] = dp[j-1][0]
for i in range(1, m):
for j in range(1, n):
if str2[i]==str1[j]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
#通过状态转移矩阵倒推出子序列
tmp=[]
s1_index=n-1
s2_index=m-1
while s1_index !=0 and s2_index !=0:
if str1[s1_index]==str2[s2_index]:
tmp.append(str1[s1_index])
s1_index=s1_index-1
s2_index=s2_index-1
else:
if dp[s2_index-1][s1_index]>dp[s2_index][s1_index-1]:
s2_index = s2_index - 1
else:
s1_index = s1_index - 1
#单独处理第0行0列
if s1_index==0:
while s2_index>=0:
if str1[0]==str2[s2_index]:
tmp.append(str1[0])
break
s2_index=s2_index-1
else:
while s1_index>=0:
if str1[s1_index]==str2[0]:
tmp.append(str1[s1_index])
break
s1_index=s1_index-1
if len(tmp)==0:
return -1
else:
return "".join(tmp[::-1])
该算法的时间复杂度和空间复杂度都是O(n^2)。
更多有趣内容，请扫码关注一波~
