递归：打印所有最长公共子序列

Question

我正在尝试使用以下代码打印所有可能的最长公共子序列

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']

Answer 1

我稍微修改了您的代码并修复了问题。我在我的代码中添加了详细代码注释。

如果你有什么不明白的请告诉我。

代码：

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']

递归：打印所有最长公共子序列

Recursion : Print all longest common subsequence

python

recursion

dynamic-programming

recursive-backtracking

longest-substring