Longest common subsequence implementation-python

2019-07-20 06:43发布

问题:

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) 

回答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 []


标签: python lcs