lcs.py

# abcde
# xabcy

# -- abcde , abcygabcdn

def lcs(word1, word2):
    memo = {}
    return find(word1, word2, 0, 0, 0, memo)

def find(word1, word2, i, j, count, memo):
    if i == len(word1) or j == len(word2):
        return count

    key = (i, j, count)
    if key in memo:
        return memo[key]

    curr_count = count
    if word1[i] == word2[j]:
        curr_count = find(word1, word2, i + 1, j + 1, count + 1, memo)

    result = max(
        curr_count,
        find(word1, word2, i + 1, j, 0, memo),
        find(word1, word2, i, j + 1, 0, memo)
    )

    memo[key] = result
    return result


x = lcs("abcde", "abcygabcdn")
print(x)