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
def edit_distance(word_a, word_b):
    """Finds edit distance between word_a and word_b

    Kwyword arguments:
    word_a -- string
    word_b -- string
    """

    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]  # this is the same as edit[length_a][length_b]
