So I am trying to implement Lowest common subsequence in Python and was trying this alternative to my previous solution. I tried using a dictionary instead of a 2-D matrix to memoize the results.
def lcs(s1, s2): cache = {} if len(s1) == 0 or len(s2) == 0: return 0 if (s1, s2) in cache: return cache[s1, s2] else: if s1[-1] == s2[-1]: cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1]) else: cache[s1, s2] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1])) print cache
It’s returning
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'
which I understand is because I am not returning anything so how can I do something like this.
return cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1])
And I am trying to implement it without using any decorators.
Advertisement
Answer
Try this
cache = {} def lcs(s1, s2): global cache if len(s1) == 0 or len(s2) == 0: return 0 if (s1, s2) in cache: return cache[(s1, s2)] else: if s1[-1] == s2[-1]: cache[(s1, s2)] = 1 + lcs(s1[:-1], s2[:-1]) else: cache[(s1, s2)] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1])) return cache[(s1, s2)]