Longest Common Subsequence (LCS) | Leetcode Day 26

Leet Code

Longest Common Subsequence (LCS) | Leetcode Day 26

April 30, 2020

Quick Jump to:

In this tutorial, let us discuss about how the Longest Common Subsequence (LCS) is found in Python.

Problem Statement:

Given two strings text1 and text2, return the length of their lcs.

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.

Problem Description:

If t1 & t2 are given 2 sequences , then common subsequences of both t1 and t2 are x,y,z. Among those if length of string x is longer than other two strings, then x is the lcs.

Example:

Let us consider the sequences like t1={S,T,U,V} and t2={S,U,T,S,V}. Here Common Subsequences of length 2 are :{S,T},{S,U},{S,V},{T,V},{U,V} and Common Subsequences of length 3 are :{S,T,U},{S,U,V}. So, {S,T,U} & {S,U,V} are the lcs.