"""
Minimum edit distance computes the cost it takes to get from one string to another string. 
This implementation uses the Levenshtein distance with a cost of 1 for insertions or deletions and a cost of 2 for substitutions.

Resource: https://en.wikipedia.org/wiki/Edit_distance

For example, getting from "intention" to "execution" is a cost of 8.
minimum_edit_distance("intention", "execution")
# 8 
"""
def minimum_edit_distance(source, target):
    n = len(source)
    m = len(target)
    D = {}

    # Initialization
    for i in range(0, n+1):
        D[i,0] = i
    for j in range(0, m+1):
        D[0,j] = j
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if source[i-1] == target[j-1]:
                D[i,j] = D[i-1, j-1]
            else:
                D[i,j] = min(
                    D[i-1, j] + 1,
                    D[i, j-1] + 1,
                    D[i-1, j-1] + 2
                )

    return D[n-1, m-1]

[]