the edit distance between two words is the minimum number of letter insertions letter deletions and letter substitutions required to transform one word into another for example the edit distance between food and money is at most four food mood mond moned money given two words a and b find the minimum number of operations required to transform one string into the other in other words find the edit distance between a and b thought process let editi j denote the edit distance between the prefixes a1 i and b1 j then the function satifies the following recurrence editi j i if j 0 j if i 0 minediti1 j 1 editi j1 1 editi1 j1 cost otherwise there are two base cases both of which occur when one string is empty and the other is not 1 to convert an empty string a into a string b of length n perform n insertions 2 to convert a string a of length m into an empty string b perform m deletions here the cost is 1 if a substitution is required or 0 if both chars in words a and b are the same at indexes i and j respectively to find the edit distance between two words a and b we need to find editlengtha lengthb time olengthalengthb space olengthalengthb finds edit distance between worda and wordb kwyword arguments worda string wordb string finds edit distance between word_a and word_b kwyword arguments word_a string word_b string this is the same as edit length_a length_b
def edit_distance(word_a, word_b):
    

    length_a, length_b = len(word_a) + 1, len(word_b) + 1

    edit = [[0 for _ in range(length_b)] for _ in range(length_a)]

    for i in range(1, length_a):
        edit[i][0] = i

    for j in range(1, length_b):
        edit[0][j] = j

    for i in range(1, length_a):
        for j in range(1, length_b):
            cost = 0 if word_a[i - 1] == word_b[j - 1] else 1
            edit[i][j] = min(edit[i - 1][j] + 1, edit[i][j - 1] + 1, edit[i - 1][j - 1] + cost)

    return edit[-1][-1]