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

Image for post
Image for post
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:

Example 2:

Example 3:

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.

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.

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.

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.

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.

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

Let us look into the complete code snippet.

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

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store