Longest Common Subsequence using Lose it or Use it

54 views Asked by At

I need to return the string of the Longest Common Subsequence of 2 strings. But the code keeps crashing, probably due to Infinite recursion? But I don't know where it happens? Am I missing a base case?

def lcs(s, t):
""" Arguments are 2 strings s and t. The function outputs a string LCS (longest common subsequence)
"""

     use = lcs(s[1:], t[1:])
     result1 = lcs(s[1:], t)
     result2 = lcs(s, t[1:])
     #lose = 

     index_list = []
     the_string = ''.join(index_list)

     if s or t == "":
         return ""
     if len(s) or len(t) == 0:
         return the_string

     if s[0] == t[0]:
         return index_list + s[0] + use

     if s[0] != t[0]:
         return result1 or result2

#Tests
#assert lcs('mens', 'chimpansee') == 'mns'
#assert lcs('gattaca', 'tacgaacta') == 'gaaca'
#assert lcs('wow', 'wauw') == 'ww'
#assert lcs('', 'wauw') == ''
#assert lcs('abcdefgh', 'efghabcd') == 'abcd'
0

There are 0 answers