Skip to content

Instantly share code, notes, and snippets.

@jleeothon
Created October 5, 2014 15:02
Show Gist options
  • Save jleeothon/ee7d174337ce15f6aaaf to your computer and use it in GitHub Desktop.
Save jleeothon/ee7d174337ce15f6aaaf to your computer and use it in GitHub Desktop.
Python: longest common subsequence (recursive)
def lcs(s, t):
if not s or not t:
return ''
if s[0] is t[0]:
return s[0] + lcs(s[1:], t[1:])
result1 = lcs(s[1:], t)
result2 = lcs(s, t[1:])
if len(result1) > len(result2):
return result1
else:
return result2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment