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 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 if first word index overflows delete all from the second word if second word index overflows delete all from the first word current letters not identical
import functools


def min_distance_up_bottom(word1: str, word2: str) -> int:
    
    len_word1 = len(word1)
    len_word2 = len(word2)

    @functools.cache
    def min_distance(index1: int, index2: int) -> int:
        
        if index1 >= len_word1:
            return len_word2 - index2
        
        if index2 >= len_word2:
            return len_word1 - index1
        diff = int(word1[index1] != word2[index2])  
        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()