Recursive solution to longest common substring not working

125 Views Asked by At

I am trying to get the longest common substring recursively but for some reason my code is not working.

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:])

    a = lcs(s[1:], t)
    b = lcs(s, t[1:])

    return b if len(a) < len(b) else a


print(lcs("JHELLOIAHDS", "NHELLOOKSÇA"))

output>> HELLOS

The two input strings are "JHELLOIAHDS" and "NHELLOOKSÇA" and the output should be HELLO. What am I doing wrong and why am I getting "HELLOS" as output?

0

There are 0 best solutions below