Implementation of Longest Common Subsequence

Question

So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more natural and intuitive way of solving the problem.

I just wanted to make sure if it's a correct way of implementing the LCS algorithm and how can I improve on it.

Using 2-D matrix

def LowestCommonSubstring(s1, s2):
    LCS = [[0 for x in range(len(s2) + 1)] for x in range(len(s1) + 1)]
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            if s1[i - 1] == s2[j - 1]:
                LCS[i][j] = 1 + LCS[i-1][j-1]
            else:
                LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1])
    return LCS[i][j]

using dictionary

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

This is the problem I'm trying to implement and for now my solution only calculates the length of the longest common substring.

Answer 1

1. You could use an explicit memoizer rather than incorporating caching into your function. This will make your function easier to understand. You can use functools lru_cache if you are using Python3.
2. You should evaluate based on truth, rather than length. len(s1) == 0 is 'bad'.
3. You can use a turnery operator to reduce the repetition of your code.
4. Your else can be removed, to prevent the arrow anti-pattern. And reduce the amount of indentation.

---

def memoize(fn)
    def inner(*args):
        try:
            return cache[args]
        except IndexError:
            cache[args] = fn(*args)
            return cache[args]
    return inner

# Natural abstracted algorithm.
@memoize
def lcs(s1, s2):
    if not s1 or not s2:
        return 0

    return (
        1 + lcs(s1[:-1], s2[:-1])
        if s1[-1] == s2[-1] else
        max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
    )