递归:打印所有最长公共子序列
Recursion : Print all longest common subsequence
我正在尝试使用以下代码打印所有可能的最长公共子序列
1-首先我找到了 LCS 长度 dp 矩阵并尝试使用递归来产生所有可能的输出。
################################################Print ALL LCS ################################333
class Solution:
def LcsHelper(self,text1,text2,dp,output,m,n):
if m<0 or n<0:
return output
if text1[m]==text2[n]:
out=[]
for elem in output.copy():
out.append(text1[m]+elem)
#output.remove(elem) # Remove this line show every possiblities
return self.LcsHelper(text1,text2,dp,out,m-1,n-1)
elif dp[m-1][n]>dp[m][n-1]:
return self.LcsHelper(text1,text2,dp,output,m-1,n)
elif dp[m-1][n]<dp[m][n-1]:
return self.LcsHelper(text1,text2,dp,output,m,n-1)
else:
out1=self.LcsHelper(text1,text2,dp,output,m-1,n)
out2=self.LcsHelper(text1,text2,dp,output,m,n-1)
return out1+out2
def printlongestCommonSubsequence(self, text1,text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return self.LcsHelper(text1,text2,dp,[""],m-1,n-1)
输入输出
s=Solution()
text1="BDCABA"
text2="ABCBDAB"
s.printlongestCommonSubsequence(text1,text2)
-----output--------------
['BDAB',
'AB',
'BAB',
'AB',
'BCAB',
'CAB',
'A',
'BA',
'A',
'BCA',
'CA',
'BCA',
'CA',
'BCBA',
'CBA']
目前,我正在获取所有可能性以及一些虚拟可能性。实际上,每次我将字符添加到输出列表时,我都需要弹出字符并将其插入到旧追加新字符中。但是当我添加行
output.remove(elem)
那么只显示LCS的一种可能性,而不是全部。请帮忙,我哪里出错了?
['BDAB']
我稍微修改了您的代码并修复了问题。我在我的代码中添加了详细代码注释。
如果你有什么不明白的请告诉我。
代码:
class Solution:
def LcsHelper(self, text1, text2, m, n, dp):
# check if the end of either sequence is reached or not
if m == 0 or n == 0:
# create a list with one empty string and return
return [""]
# check if the last character of text1 and text2 matches
if text1[m - 1] == text2[n - 1]:
# ignore the last characters of text1 and text2 and find all LCS of substring text1[0 … m-2], text2[0 … n-2] and store it in a list
lcs = self.LcsHelper(text1, text2, m - 1, n - 1, dp)
# append current character text1[m-1] or text2[n-1] to all LCS of substring text1[0 … m-2] and text2[0 … n-2]
for i in range(len(lcs)):
lcs[i] = lcs[i] + (text1[m - 1])
return lcs
# we will reach here when the last character of text1 and text2 don't match
# if a top cell of the current cell has more value than the left cell,
# then ignore the current character of string text1 and find all LCS of substring text1[0 … m-2], text2[0 … n-1]
if dp[m - 1][n] > dp[m][n - 1]:
return self.LcsHelper(text1, text2, m - 1, n, dp)
# if a left cell of the current cell has more value than the top cell,
# then ignore the current character of string text2 and find all LCS of substring text1[0 … m-1], text2[0 … n-2]
if dp[m][n - 1] > dp[m - 1][n]:
return self.LcsHelper(text1, text2, m, n - 1, dp)
# if the top cell has equal value to the left cell, then consider both characters
top = self.LcsHelper(text1, text2, m - 1, n, dp)
left = self.LcsHelper(text1, text2, m, n - 1, dp)
# merge two lists and return
return top + left
def printlongestCommonSubsequence(self, text1, text2):
# calculate length of text1 and text2
m, n = len(text1), len(text2)
# dp[i][j] stores the length of LCS of substring text1[0 … i-1] and text2[0 … j-1]
dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
# fill the lookup dp table in a bottom-up manner
for i in range(1, m + 1):
for j in range(1, n + 1):
# check if the current character of text1 and text2 matches
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
# otherwise, the current character of text1 and text2 don't match
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# find all the longest common sequences
lcs = self.LcsHelper(text1, text2, m, n, dp)
# since a list can contain duplicates, so remove duplicates using set and return unique LCS list
return list(set(lcs))
s=Solution()
text1="BDCABA"
text2="ABCBDAB"
print(s.printlongestCommonSubsequence(text1, text2))
输出:
['BDAB', 'BCBA', 'BCAB']
我正在尝试使用以下代码打印所有可能的最长公共子序列
1-首先我找到了 LCS 长度 dp 矩阵并尝试使用递归来产生所有可能的输出。
################################################Print ALL LCS ################################333
class Solution:
def LcsHelper(self,text1,text2,dp,output,m,n):
if m<0 or n<0:
return output
if text1[m]==text2[n]:
out=[]
for elem in output.copy():
out.append(text1[m]+elem)
#output.remove(elem) # Remove this line show every possiblities
return self.LcsHelper(text1,text2,dp,out,m-1,n-1)
elif dp[m-1][n]>dp[m][n-1]:
return self.LcsHelper(text1,text2,dp,output,m-1,n)
elif dp[m-1][n]<dp[m][n-1]:
return self.LcsHelper(text1,text2,dp,output,m,n-1)
else:
out1=self.LcsHelper(text1,text2,dp,output,m-1,n)
out2=self.LcsHelper(text1,text2,dp,output,m,n-1)
return out1+out2
def printlongestCommonSubsequence(self, text1,text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1]+1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return self.LcsHelper(text1,text2,dp,[""],m-1,n-1)
输入输出
s=Solution()
text1="BDCABA"
text2="ABCBDAB"
s.printlongestCommonSubsequence(text1,text2)
-----output--------------
['BDAB',
'AB',
'BAB',
'AB',
'BCAB',
'CAB',
'A',
'BA',
'A',
'BCA',
'CA',
'BCA',
'CA',
'BCBA',
'CBA']
目前,我正在获取所有可能性以及一些虚拟可能性。实际上,每次我将字符添加到输出列表时,我都需要弹出字符并将其插入到旧追加新字符中。但是当我添加行
output.remove(elem)
那么只显示LCS的一种可能性,而不是全部。请帮忙,我哪里出错了?
['BDAB']
我稍微修改了您的代码并修复了问题。我在我的代码中添加了详细代码注释。
如果你有什么不明白的请告诉我。
代码:
class Solution:
def LcsHelper(self, text1, text2, m, n, dp):
# check if the end of either sequence is reached or not
if m == 0 or n == 0:
# create a list with one empty string and return
return [""]
# check if the last character of text1 and text2 matches
if text1[m - 1] == text2[n - 1]:
# ignore the last characters of text1 and text2 and find all LCS of substring text1[0 … m-2], text2[0 … n-2] and store it in a list
lcs = self.LcsHelper(text1, text2, m - 1, n - 1, dp)
# append current character text1[m-1] or text2[n-1] to all LCS of substring text1[0 … m-2] and text2[0 … n-2]
for i in range(len(lcs)):
lcs[i] = lcs[i] + (text1[m - 1])
return lcs
# we will reach here when the last character of text1 and text2 don't match
# if a top cell of the current cell has more value than the left cell,
# then ignore the current character of string text1 and find all LCS of substring text1[0 … m-2], text2[0 … n-1]
if dp[m - 1][n] > dp[m][n - 1]:
return self.LcsHelper(text1, text2, m - 1, n, dp)
# if a left cell of the current cell has more value than the top cell,
# then ignore the current character of string text2 and find all LCS of substring text1[0 … m-1], text2[0 … n-2]
if dp[m][n - 1] > dp[m - 1][n]:
return self.LcsHelper(text1, text2, m, n - 1, dp)
# if the top cell has equal value to the left cell, then consider both characters
top = self.LcsHelper(text1, text2, m - 1, n, dp)
left = self.LcsHelper(text1, text2, m, n - 1, dp)
# merge two lists and return
return top + left
def printlongestCommonSubsequence(self, text1, text2):
# calculate length of text1 and text2
m, n = len(text1), len(text2)
# dp[i][j] stores the length of LCS of substring text1[0 … i-1] and text2[0 … j-1]
dp = [[0 for x in range(n + 1)] for y in range(m + 1)]
# fill the lookup dp table in a bottom-up manner
for i in range(1, m + 1):
for j in range(1, n + 1):
# check if the current character of text1 and text2 matches
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
# otherwise, the current character of text1 and text2 don't match
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# find all the longest common sequences
lcs = self.LcsHelper(text1, text2, m, n, dp)
# since a list can contain duplicates, so remove duplicates using set and return unique LCS list
return list(set(lcs))
s=Solution()
text1="BDCABA"
text2="ABCBDAB"
print(s.printlongestCommonSubsequence(text1, text2))
输出:
['BDAB', 'BCBA', 'BCAB']