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!

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]