Dynamic programming

edit_distance.py

def main():
    result = edit_distance("fox", "fab")
    print(result)

def edit_distance(str1, str2):
    len1 = len(str1)
    len2 = len(str2)
    maxtrix = [[i for j in range(len2 +1)] for i in range(len1 + 1)]
    maxtrix[0] = [i for i in range(len1 + 1)]

    for i in range(1, len1):
        for j in range(1, len2):
            if str1[i-1] == str2[j-1]:
                maxtrix[i][j] = maxtrix[i-1][j-1]
            else:
                maxtrix[i][j] = min(maxtrix[i][j-1] + 1, maxtrix[i-1][j] + 1, maxtrix[i-1][j-1] + 1)