#!/usr/bin/env python3

from functools import lru_cache

memoize = lru_cache(None)


def levenshtein_distance(s, t):
    @memoize
    def d(i, j):
        return (
            i
            if j == 0
            else j
            if i == 0
            else d(i - 1, j - 1)
            if s[i - 1] == t[j - 1]
            else min(d(i - 1, j) + 1, d(i, j - 1) + 1, d(i - 1, j - 1) + 1)
        )

    return d(len(s), len(t))


assert levenshtein_distance("snowy", "sunny") == 3