lcs.py

CACHE = {}

def lcs2(frm, to):

    len_frm = len(frm)
    len_to = len(to)

    # Create a table
    # len_to is height, len_frm is width
    table = [[0] * len_to 
             for _ in xrange(len_frm)]

    for i in xrange(len_frm-1, -1, -1):
        for j in xrange(len_to-1, -1, -1):

            # 0 when one of the two is zero
            if i >= len_frm -1 or j >= len_to -1:
                table[i][j] = 0

            else:
                results = []
                # Check when i+1 and j
                results.append(table[i+1][j])

                # Check when i and j+1
                results.append(table[i][j+1])

                # Check when i- and j+1
                addition = 1 if frm[i] == to[j] else 0
                results.append(table[i+1][j+1] + addition)

                # Add results
                table[i][j] = max(results)

    return table[0][0]

def lcs(frm, to):

    # Base case
    if 0 in [len(frm), len(to)]:
        return 0

    try:
        return CACHE[tuple(frm), tuple(to)]
    except KeyError:
        pass

    first_frm, rest_frm = frm[0], frm[1:]
    first_to, rest_to = to[0], to[1:]

    results = []
    # Case 1 frm-1 and to
    results.append(lcs(rest_frm, to))

    # Case 2 frm and to-1
    results.append(lcs(frm, rest_to))

    # Case 3 frm-1 and to-1
    addition = 1 if first_frm == first_to else 0
    results.append(lcs(rest_frm, rest_to) + addition)

    # Return the biggest
    CACHE[tuple(frm), tuple(to)] = max(results)
    return max(results)



if __name__ == '__main__':
    print lcs2("n e m a t o d e  k n o w l e d g e".split(' '),
              "e m p t y  b o t t l e".split(' '))