Grokking Dynamic Programming Patterns for Coding Interviews
Vote

0% completed

​

Solution: Longest Common Subsequence

Problem Statement

Given two strings 's1' and 's2', find the length of the longest subsequence which is common in both the strings.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: s1 = "abdca"
       s2 = "cbda"
Output: 3
Explanation: The longest common subsequence is "bda".

Example 2:

Input: s1 = "passport"
       s2 = "ppsspt"
Output: 5
Explanation: The longest common subsequence is "psspt".

.....

.....

.....

Like the course? Get enrolled and start learning!
G

Gary

· 4 years ago

In bottom-up solution,

"If the character s1[i] matches s2[j], the length of the common subsequence would be one plus the length of the common subsequence till the i-1 and j-1 indexes in the two respective strings," which is intuitive.

But the actual code checks for s1[i-1] ==s2[i-2]:

for i in range(1, n1+1): for j in range(1, n2+1): if s1[i - 1] == s2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1]

When i try to write it as follows, I get 4 instead of 5 for "passport"/"ppsspt"

max_length = 0 for s1_idx in range (1, len(s1)): for s2_idx in range(1, len(s2)): if s1[s1_idx] == s2[s2_idx]: dp[s1_idx][s2_idx] = 1 + dp[s1_idx-1][s2_idx-1] else: dp[s1_idx][s2_idx] = max(dp[s1_idx-1][s2_idx], dp[s1_idx][s2_idx-1])

max_length = max(max_length, dp[s1_idx][s2_idx])

return max_length

Is there a way to

S

Shan

· 4 years ago

What is time and space complexity of top down with memo?

Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findLCSLength(self, s1, s2):
    m = len(s1) + 1
    n = len(s2) + 1
    table = [[0] * n for _ in range(m)]
    
    for i in range(1, m):
      for j in range(1, n):
        if s1[i - 1] == s2[j - 1]:
          table[i][j] = table[i - 1][j - 1] + 1
        else:
          table[i][j] = max(table[i][j - 1],  table[i - 1][j])
        
    return table[-1][-1]