Levenshtein Distance

def initMinEditDistTable(source, target):
    xLen = len(target)
    yLen = len(source)

    minEditDistTable = [[0 for x in range(xLen + 2)] for y in range(yLen + 2)]

    minEditDistTable[0][0] = "#"
    minEditDistTable[0][1] = "#"
    minEditDistTable[1][0] = "#"

    for x in range(xLen):
        minEditDistTable[0][x + 2] = target[x]
        minEditDistTable[1][x + 2] = x + 1

    for y in range(yLen):
        minEditDistTable[y + 2][0] = source[y]
        minEditDistTable[y + 2][1] = y + 1

    return minEditDistTable

def calcMinEditDistTable(source, target):
    xLen = len(target)
    yLen = len(source)

    minEditDistTable = initMinEditDistTable(source, target)

    for x in range(xLen):
        for y in range(yLen):
            if source[y] == target[x]:
                subCost = 0
            else:
                subCost = 2

            up = minEditDistTable[y + 1][x + 2] + 1
            left = minEditDistTable[y + 2][x + 1] + 1
            diag = minEditDistTable[y + 1][x + 1] + subCost


            minEditDistTable[y + 2][x + 2] = min(up, left, diag)

    return minEditDistTable



test = calcMinEditDistTable("intention", "execution")

print('\n'.join([''.join(['{:>4}'.format(item) for item in row]) for row in test]))