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

Solution Review: Longest Common Substring

Understand how to solve the longest common substring problem using various approaches including simple recursion, top-down memoization, and bottom-up dynamic programming with tabulation. Learn to optimize space complexity while maintaining time efficiency using these methods.

We'll cover the following...

Solution 1: Simple recursion

Python 3.5
def lcs_(str1, str2, i, j, count):
  # base case of when either of string has been exhausted
  if i >= len(str1) or j >= len(str2):  
    return count
  # if i and j character matches, increment the count and compare the rest of the strings
  if str1[i] == str2[j]:     
    count = lcs_(str1, str2, i+1, j+1, count+1)
  # compare str1[1:] with str2, str1 with str2[1:], and take max of current count and these two results
  return max(count, lcs_(str1, str2, i+1, j, 0), lcs_(str1, str2, i, j+1, 0))
  
def lcs(str1, str2):
  return lcs_(str1, str2, 0, 0, 0)
print(lcs("hello", "elf"))

Explanation

Let’s look at this problem on a smaller scale. We are comparing each character one by one with the other string. There can be three possibilities for ith^{th} character of str1 and jth^{th} character of str2. If both characters match, these could be part of a common substring meaning we should count this length (lines 6-7). In the case that these characters do not match, we could have two further possibilities:

  • ith^{th} character might match with (j+1)th^{th} character.
  • jth^{th} character might match with (i+1)th^{th}
...