Longest Common Subsequence in two ways: Dynamic Programming, Recursion

LCS.py

#!/usr/bin/env python
# encoding:utf-8


def display(table):
    for line in table:
        for i in line:
            print(" ".join(i))
        print()


def LCSNDynamicProgramming(x, y):
    '''
    Longest Common Subsequence Number in Dynamic Programming
    '''
    w = len(x)
    h = len(y)
    table = [[0 for x in range(w + 1)] for y in range(h + 1)]
    for i in range(w):
        for j in range(h):
            if x[i] == y[j]:
                table[j + 1][i + 1] = table[j][i] + 1
            else:
                table[j + 1][i + 1] = max(table[j + 1][i], table[j][i + 1])
    return table[h][w]


def LCSNRecursion(x, y):
    '''
    Longest Common Subsequence Number in Recursion
    '''
    # Recursion Base
    if len(x) == 0 or len(y) == 0:
        return 0
    if x[-1] == y [-1]:
        # Decrease and Conquer
        return LCSNRecursion(x[0:-1], y[0:-1]) + 1
    else:
        # Divide and Conquer
        return max(LCSNRecursion(x[0:-1], y), LCSNRecursion(x, y[0:-1]))

def LCSRRecursion(x, y):
    '''
    Longest Common Subsequence Result in Recursion
    '''
    # Recursion Base
    if len(x) == 0 or len(y) == 0:
        return ""
    if x[-1] == y [-1]:
        # Decrease and Conquer
        return LCSRRecursion(x[0:-1], y[0:-1]) + x[-1]
    else:
        # Divide and Conquer
        a = LCSRRecursion(x[0:-1], y)
        b = LCSRRecursion(x, y[0:-1])
        if len(a) > len(b):
            return a
        else:
            return b


def main():
    '''
    x = "educational"
    y = "advantage"
    '''
    x = "Here's another solution, which repeats lists to build the next rows of the list. The i-th line of the list consists of i numbers 2, followed by one integer 1, followed by n-i-1 zeros"
    y = "You can use nested generators to create two-dimensional arrays, placing the generator of the list which is a string, inside the generator of all the strings. Recall that you can create a list of n rows and m columns using the generator (which creates a list of n elements, where each element is a list of m zeros):"
    print("x = %r" % (x))
    print("y = %r" % (y))
    print("LCSNDynamicProgramming: ", LCSNDynamicProgramming(x, y))
    print("LCSNRecursion: ", LCSNRecursion(x, y))

if __name__ == '__main__':
    main()