Calculate edit distance with simple (memoized) recursive algorithm

edit_distance.py

def distance(s, t, cache=None):
    """Return minimum edit distance between s and t, where an edit
    is a character substitution, deletion, or addition.
    """
    if not s:
        return len(t)
    if not t:
        return len(s)

    if cache is None:
        cache = {}
    key = (s, t)
    if key in cache:
        return cache[key]

    if s[0] == t[0]:
        # First chars equal, return edit distance of the rest
        d = distance(s[1:], t[1:], cache)
    else:
        # First chars not equal, it's 1 + edit distance of the rest
        d = 1 + min(
            distance(s[1:], t[1:], cache),  # substitution of first chars
            distance(s[1:], t, cache),      # delete first char of s
            distance(s, t[1:], cache),      # delete first char of t (addition)
        )

    cache[key] = d
    return d