Longest Common Subsequence(Bottom-Up) — Day 53(Python)

Photo by davide ragusa on Unsplash

Today’s article is the final part of the three-part series of Longest Common Subsequence(LCS) problem. You can follow this link if you need to understand how to solve the LCS problem using top-down.

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.

If there is no common subsequence, return 0.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

Constraints:

• 1 <= text1.length <= 1000
• 1 <= text2.length <= 1000
• The input strings consist of lowercase English characters only.

Before looking into the Bottom-Up approach, let us recall the Top-Down approach.

class FindLongest:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[float('-inf') for j in range(len(text2)+1)]for i in range(len(text1)+1)]
        def longest(t1, t2):
            if len(t1) == 0 or len(t2) == 0:
                return 0
            if(memo[len(t1)][len(t2)] != float('-inf')):
                return memo[len(t1)][len(t2)]
            
            if t1[-1] == t2[-1]:
                memo[len(t1)][len(t2)] =  1+(longest(t1[:-1],t2[:-1]))
                return memo[len(t1)][len(t2)]
            else:
                memo[len(t1)][len(t2)] =  max(longest(t1[:-1],t2), longest(t1,t2[:-1]))
                return memo[len(t1)][len(t2)]
        longest(text1, text2)
        
        return memo[-1][-1]

We have seen earlier, converting a Top-Down approach to a Bottom-Up is easy.

Similar to the Top-Down approach, we need a 2D array that will store the intermediate results. The size of the 2D is array will the length of both the strings. We will initialize the cells with MIN_INT value.

memo = [[float('-inf') for j in range(len(text2)+1)]for i in range(len(text1)+1)]

Let us move to the next part, initialization for the 1st row and the 1st column.

We know when any of the string is empty, there cannot be anything that we can term as common. Since the 1st row represents empty string1 and the 1st column represents empty string2, we will be initializing both with 0.

for i in range(len(memo)):
    for j in range(len(memo[0])):
        if(i==0 or j==0):
           memo[i][j]=0

We next move to the gist of the algorithm.

The problem states, we need to find the longest subsequence in given strings. Let us recall the algorithm from the top-down approach.

if t1[-1] == t2[-1]:
   memo[len(t1)][len(t2)] = 1+(longest(t1[:-1],t2[:-1]))
   return memo[len(t1)][len(t2)]
else:
   memo[len(t1)][len(t2)] = max(longest(t1[:-1],t2), longest(t1,t2[:-1]))

We know, the rows represent string1 and columns represent string2. Replace length of t1 with “i” and length of t2 with “j”. Also, remember to replace the function calls with the Dynamic Programming table.

elif text1[i-1] == text2[j-1]:
   memo[i][j] = 1 + memo[i-1][j-1]
else:
   memo[i][j] = max(memo[i-1][j], memo[i][j-1])

In the end, return the last cell value as the result.

Let us look into the complete code snippet.

class FindLongest:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[float('-inf') for j in range(len(text2)+1)]for i in range(len(text1)+1)]
        for i in range(len(memo)):
            for j in range(len(memo[0])):
                if i == 0 or j == 0:
                    memo[i][j] = 0
                elif text1[i-1] == text2[j-1]:
                    memo[i][j] = 1 + memo[i-1][j-1]
                else:
                    memo[i][j] = max(memo[i-1][j], memo[i][j-1])
        return memo[-1][-1]

Complexity analysis.

Time Complexity

We are traversing through a 2D array of size M*N, hence the time complexity is O(M*N) where M is the size of string1 and N is the size of string2.

Space Complexity.

We are creating a 2D array of size M*N, hence the space complexity is O(M*N) where M is the size of string1 and N is the size of string2.

Link to Aditya Verma’s video