Analytics Vidhya
Published in

Analytics Vidhya

Longest Common Subsequence

Photo by Markus Spiske on Unsplash
  1. Create two counters idx1 and idx2 starting at 0. Our recursive function will compute the LCS of seq1[idx1:] and seq2[idx2:]
  2. If seq1[idx1] and seq2[idx2] are equal, then this character belongs to the LCS of seq1[idx1:] and seq2[idx2:] (why?). Further the length this is LCS is one more than LCS of seq1[idx1+1:] and seq2[idx2+1:]
def lcs_recursive(seq1, seq2, idx1=0, idx2=0):
if idx1 == len(seq1) or idx2 == len(seq2):
return 0
elif seq1[idx1] == seq2[idx2]:
return 1 + lcs_recursive(seq1, seq2, idx1+1, idx2+1)
else:
option1 = lcs_recursive(seq1, seq2, idx1+1, idx2)
option2 = lcs_recursive(seq1, seq2, idx1, idx2+1)
return max(option1, option2)
def lcs_memo(seq1, seq2):
memo = {}
def recurse(idx1=0, idx2=0):
key = (idx1, idx2)
if key in memo:
return memo[key]
elif idx1 == len(seq1) or idx2 == len(seq2):
memo[key] = 0
elif seq1[idx1] == seq2[idx2]:
memo[key] = return 1 + recurse(idx1+1, idx2+1)
else:
memo[key] = max(recurse(idx1+1, idx2), recurse(idx1, idx2+1))
return memo[key]
return recurse(0, 0)
  1. Create a table of size (n1+1) * (n2+1) initialized with 0s, where n1 and n2 are the lengths of the sequences. table[i][j] represents the longest common subsequence of seq1[:i] and seq2[:j]. Here's what the table looks like (source: Kevin Mavani, Medium).
def lcs_dp(seq1, seq2):
n1, n2 = len(seq1), len(seq2)
table = [[0 for x in range(n2)] for x in range(n1)]
for idx1 in range(n1):
for idx2 in range(n2):
if seq1[idx1] == seq2[idx2]:
table[i+1][j+1] = 1 + table[i][j]
else:
table[i+1][j+1] = max(table[i][j+1], table[i+1][j])
return table[-1][-1]

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store