# Minimum edit distance algorithm (Wagner-Fischer). Note that this isn't a very efficient algorithm (it runs in
# exponential time, and n^2 space).

def minEditDistance(string1, string2):
    # this will be a 2D array to store the distance. Think of it as n*m matrix, which we initially fill with 0s
    array = [[0 for i in range(len(string1)+1)] for j in range(len(string2)+1)];
    # fill the top row of the matrix
    for j in range(len(string1) + 1):
        array[0][j] = j

    # fill the first column
    for i in range(len(string2) + 1):
        array[i][0] = i

    for i in range(1, len(string2) + 1):
        for j in range(1, len(string1) + 1):
            if string1[j-1] == string2[i-1]:
                array[i][j] = array[i-1][j-1]
            else:
                array[i][j] = min (min ((array[i-1][j-1] + 2), (array[i][j-1] + 1)), (array[i-1][j] + 1))

    return array[len(string2)][len(string1)]

print("to verify the pen and paper exercis:")
print("'refa' to 'fear':    ", minEditDistance("refa", "fear"))
print("'drive' to 'brief':  ", minEditDistance("drive", "brief"))
print("'drive' to 'divers': ", minEditDistance("drive", "divers"))