Recursion : Print all longest common subsequence

Question

Iam trying to print all possible longest common subsequence using below code

1-Firstly i found LCS length dp matrix and trying using recursion to produce all possible outputs.

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

Input and output

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

Current, Iam getting every possibilities along with some dummy possibilities. actually every time i add the character to the output list, i need to popout the character and insert to it as old append with new. But when i add the line

output.remove(elem)

It then only show one possibility of LCS, not all. Please help, where iam going wrong?

['BDAB']

Answer 1

I modify your code a bit and fix issues. I add details code comments in my code.

If you don't understand anything please let me know.

Code:

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

Output:

['BDAB', 'BCBA', 'BCAB']