lcs.py

count = 0

def lcs(w1, w2, i=0, j=0, cache=None):
    global count

    cache = cache or {}

    if (i, j) in cache:
        return cache[(i, j)]

    count += 1

    if not w1[i:] or not w2[j:]:
        cache[(i, j)] = 0
        return 0
    
    if w1[i] == w2[j]:
        val = 1 + lcs(w1, w2, i+1, j+1, cache)
        cache[(i, j)] = val
        return val

    val = max(
            lcs(w1, w2, i, j+1, cache),
            lcs(w1, w2, i+1, j, cache),
    )
    cache[(i, j)] = val
    return val


count = 0
print(lcs("i am a longer string", "longer"))
print(count)