Longest Common Subsequence

We can think of subsequences like binary strings.

rules are not all that great

1111111110000000000000011111

Ursinus college students are great students

01000100001000000000100000000010010111111111000000000

We know there are $2^N$ unique binary strings of length $N$, so a brute force algorithm would be exponential at best. Instead, we're going to make a recursive operation to work backwards. Your job in the next exercise will be to use memoization to make this faster, since there are many overlapping subproblems that you can remember to cut off branches in the recursion

In [14]:
def LCS(s1, s2):
    """
    Parameters
    ----------
    s1: string
        First string
    s2: string
        Second string
    """
    if len(s1) == 0 or len(s2) == 0:
        return 0
    if s1[-1] == s2[-1]:
        return 1 + LCS(s1[0:-1], s2[0:-1])
    else:
        return max(LCS(s1[0:-1], s2), LCS(s1, s2[0:-1]))
In [15]:
print(LCS("school", "fool"))

3
In [16]:
print(LCS("ph one..", "phones"))

5
In [ ]: