Problem 1143

(Last updated: )

Question statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Solution

Since the common substring can start and end at any index for both the given strings, I opted for a 2-d DP approach.

Main idea:

Initialize a 2-d DP array with the intention to store the longest common subsequence of text1 and text2 between indices [0:i] of text1 and [0:j] of text2, in dp[i][j]. Now, suppose the left index i is fixed, as the right index j scans the second word. If the current letter text2[j] is equal to text1[i], then we can tack on this letter to the longest common subsequence encountered so far. So add 1 to dp[i-1][j-1]. If the two letters are not the same, then we can choose to either keep text2[j] and drop text1[i], or keep text1[i] and drop text2[j]. So in dp[i][j] we will store the maximum of these two outcomes that correspond to dp[i-1][j] and dp[i][j-1] respectively. Finally return dp[len(text1)-1][len(text2)-1].

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    if(text1 == text2):
        return len(text1)
    n1= len(text1)+1
    n2 = len(text2)+1
    dp = [[0 for _ in range(n2)] for _ in range(n1)]
    for i in range(n1):
        for j in range(n2):
            if(i==0 or j==0):
                dp[i][j] = 0
            elif(text1[i-1]==text2[j-1]):
                dp[i][j] = dp[i-1][max(0,j-1)]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][max(0,j-1)])
    
    return dp[n1-1][n2-1]

Comments:

Time complexity: O($n^2$) where n = max(len(text1), len(text2)).

At the time of submission, the above solution passes leetcode submission cases in 577ms, beats 44.89% of users. It uses 25.25MB of memory, beating 84.36% of users.