Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: Longest Common Subsequence

Understand how to solve the Longest Common Subsequence problem using different dynamic programming approaches including simple recursion, top-down memoization, bottom-up tabulation, and space-optimized methods. Learn to analyze and optimize time and space efficiency in each approach for effective algorithm design.

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 ...