Author  : Alexander Pantyukhin Date    : October 14, 2022 This is an implementation of the upbottom approach to find edit distance. The implementation was tested on Leetcode: https:leetcode.comproblemseditdistance Levinstein distance Dynamic Programming: up  down.  mindistanceupbottomintention, execution 5  mindistanceupbottomintention,  9  mindistanceupbottom,  0  mindistanceupbottomzooicoarchaeologist, zoologist 10 if first word index overflows  delete all from the second word if second word index overflows  delete all from the first word
import functools


def min_distance_up_bottom(word1: str, word2: str) -> int:
    """
    >>> min_distance_up_bottom("intention", "execution")
    5
    >>> min_distance_up_bottom("intention", "")
    9
    >>> min_distance_up_bottom("", "")
    0
    >>> min_distance_up_bottom("zooicoarchaeologist", "zoologist")
    10
    """
    len_word1 = len(word1)
    len_word2 = len(word2)

    @functools.cache
    def min_distance(index1: int, index2: int) -> int:
        # if first word index overflows - delete all from the second word
        if index1 >= len_word1:
            return len_word2 - index2
        # if second word index overflows - delete all from the first word
        if index2 >= len_word2:
            return len_word1 - index1
        diff = int(word1[index1] != word2[index2])  # current letters not identical
        return min(
            1 + min_distance(index1 + 1, index2),
            1 + min_distance(index1, index2 + 1),
            diff + min_distance(index1 + 1, index2 + 1),
        )

    return min_distance(0, 0)


if __name__ == "__main__":
    import doctest

    doctest.testmod()
