Logic error in my Longest Common Subsequence python

Question

I have implemented solution of Longest Common Subsequence using Dynamic programming in python. For those who don't know LCS here's the link.

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_longest_common_subsequence.htm

My code is not returning the the most optimal answer. What is wrong in my logic ?

import enum

class LCS:

    class Dir(enum.Enum):
        up = 1
        diagonal = 2
        left = 3
        none = 0

    def LCS(self, x, y):
        self.DP = {}
        m = len(x) - 1
        n = len(y) - 1
        self.recursion(x, y, m, n)
        print(self.DP)
        self.printLCS(x, m, n)

    def recursion(self, x, y, i, j):
        if i == 0 or j == 0:
            return [0, self.Dir.none]
        else:
            if (i, j) not in self.DP:
                if x[i] == y[j]:
                    cost = self.recursion(x, y, i - 1, j - 1)[0] + 1
                    dir = self.Dir.diagonal
                else:
                    first = self.recursion(x, y, i - 1, j)
                    second = self.recursion(x, y, i, j - 1)
                    if first[0] >= second[0]:
                        cost = first[0]
                        dir = self.Dir.up
                    else:
                        cost = second[0]
                        dir = self.Dir.left

                self.DP[(i, j)] = [cost, dir]

        return self.DP[(i, j)]

    def printLCS(self, string, i, j):
        if i == 0 or j == 0:
            return
        elif self.DP[(i, j)][1] == self.Dir.diagonal:
            self.printLCS(string, i - 1, j - 1)
            print(string[i], end="")
        elif self.DP[(i, j)][1] == self.Dir.up:
            self.printLCS(string, i - 1, j)
        else:
            self.printLCS(string, i, j - 1)


x = "BDCABA"
y = "ABCBDAB"
sol = LCS()
sol.LCS(x, y)

Expected = "BCBA", Actual = "DAB"

Milad Rezaei Hajidehi Milad Rezaei Hajidehi · Accepted Answer · 2018-07-28T19:01:38

the problem is your base states.

the string in python is 0-base, cause of this the first character of string s is not s[1] its s[0] and you must end your recursion when you reach before first element not at first element.

just replace if i == 0 or j == 0: with if i == -1 or j == -1: in function printLCS and recursion then you will get output BDAB which is the one of correct answers.

Logic error in my Longest Common Subsequence python

1 Answers