Skip to content

Instantly share code, notes, and snippets.

@phraniiac phraniiac/lcs.py
Created Feb 14, 2020

Embed
What would you like to do?
def lcs(str1, str2):
l = [[0] * len(str2) for i in range(len(str1))]
for r in range(len(str1)):
for c in range(len(str2)):
if r > 0 and c > 0:
l[r][c] = max(l[r-1][c], l[r][c-1])
if str1[r] == str2[c]:
l[r][c] = max(l[r - 1][c - 1] + 1, l[r][c])
if r == 0 or c == 0:
if r == 0 and c > 0:
l[r][c] = max(l[r][c], l[r][c - 1])
if c == 0 and r > 0:
l[r][c] = max(l[r-1][c], l[r][c])
if str1[r] == str2[c]:
l[r][c] = max(1, l[r][c])
return l[len(str1) - 1][len(str2) - 1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.