Longest common subsequence implementation-python

Question

I have implemented the longest common subsequence problem as instructed in this video. It just execute first set of code and produces an empty list. What is wrong with this implementation?

def lcs_recursive(xlist,ylist):
    if not xlist or ylist:
        return []
    x,xs,y,ys, = xlist[0],xlist[1:],ylist[0],ylist[1:]
    if x == y:
        return [x] + lcs_recursive(xs,ys)
    else:
        return max(lcs_recursive(xlist,ys),lcs_recursive(xs,ylist),key=len)



s1 = 'abc'
s2 = 'aeb'

print lcs_recursive(s1,s2) 

Dniester

Why not use google before posting it here?rosettacode.org/wiki/Longest_common_subsequence#Recursion_7 – Neurasthenic

Answer 1

if not xlist or ylist: will evaluate as if (not xlist) or (ylist) and as such if you pass in something Truthy (like a non-empty list) to ylist it will always evaluate to True. You probably want:

if not xlist or not ylist:
    return []

Alternatively you could use:

if not all([xlist, ylist]):
    return []

Choe

Oh..I didn't notice it. Thanks. – Dniester