Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: Longest Common Subsequence

Solution Review: Longest Common Subsequence

In this lesson, we will go over some solutions to the classic dynamic programming problem of the longest common subsequence.

We'll cover the following...

Solution 1: Simple recursion #

Python 3.5
# helper function with updated signature: i is current index in str1, j is current index in str2
def LCS_(str1, str2, i, j): 
    if i == len(str1) or j == len(str2): # base case
        return 0
    elif str1[i] == str2[j]:  # if current characters match, increment 1
        return 1 + LCS_(str1, str2, i+1, j+1)
    # else take max of either of two possibilities
    return max(LCS_(str1, str2, i+1, j), LCS_(str1, str2, i, j+1))
def LCS(str1, str2):
    return LCS_(str1, str2, 0, 0)
print(LCS("bed", "read"))

Explanation

The algorithm is pretty intuitive, we start comparing str1 and str2 at the first characters. If the characters match we can simply move one position ahead in both str1 and str2 (lines 5-6). If the characters do not match, we need to find the possibility that yields maximum count from either moving one position ahead in str1 or moving one position ahead in str2 (line 8). As our base case, we return 00 when either of our strings end is reached (lines 3-4).

Time complexity

At each point we can have a max of two possibilities, we can move one character ahead in either string. If lengths of strings are mm and nn respectively, we will have an overall time complexity bounded by O(2m+n^{m+n}).

Solution 2: Top-down dynamic programming

Let’s take a look at how this problem satisfies both the prerequisites of dynamic programming.

Optimal substructure

If we have a pair of strings str1 and str2 with lengths of n and m, we could construct their optimal solution if we ...