dynamic_programming.longest_common_subsequence

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily continuous. Example:”abc”, “abg” are subsequences of “abcdefgh”.

Attributes

a

Functions

longest_common_subsequence(x, y)

Finds the longest common subsequence between two strings. Also returns the

Module Contents

dynamic_programming.longest_common_subsequence.longest_common_subsequence(x: str, y: str)

Finds the longest common subsequence between two strings. Also returns the The subsequence found

Parameters

x: str, one of the strings y: str, the other string

Returns

L[m][n]: int, the length of the longest subsequence. Also equal to len(seq) Seq: str, the subsequence found

>>> longest_common_subsequence("programming", "gaming")
(6, 'gaming')
>>> longest_common_subsequence("physics", "smartphone")
(2, 'ph')
>>> longest_common_subsequence("computer", "food")
(1, 'o')
>>> longest_common_subsequence("", "abc")  # One string is empty
(0, '')
>>> longest_common_subsequence("abc", "")  # Other string is empty
(0, '')
>>> longest_common_subsequence("", "")  # Both strings are empty
(0, '')
>>> longest_common_subsequence("abc", "def")  # No common subsequence
(0, '')
>>> longest_common_subsequence("abc", "abc")  # Identical strings
(3, 'abc')
>>> longest_common_subsequence("a", "a")  # Single character match
(1, 'a')
>>> longest_common_subsequence("a", "b")  # Single character no match
(0, '')
>>> longest_common_subsequence("abcdef", "ace")  # Interleaved subsequence
(3, 'ace')
>>> longest_common_subsequence("ABCD", "ACBD")  # No repeated characters
(3, 'ABD')

dynamic_programming.longest_common_subsequence.a = 'AGGTAB'