edit_distance.py

def edit_distance(string_x: str, string_y: str) -> list(list()):
    # Left-pad a blank character to both strings
    string_x = ' ' + string_x
    string_y = ' ' + string_y
    
    # Obtain the length of the padded string
    len_x = len(string_x)
    len_y = len(string_y)
    
    # Initializing the distance matrix, we know that the first row and column
    # can be at most n or m.
    dist_mat = [[0] * len_y for i in range(len_x)]  
    for i in range(len_x):
        dist_mat[i][0] = i
    for j in range (len_y):
        dist_mat[0][j] = j
    
    # Calculating the distance matrix row by row.
    for j in range(1, len_y):
        for i in range(1, len_x):
            s = 1
            # Characters are the same at i,j so we make no changes
            if (string_x[i] == string_y[j]):
                s = 0

            dist_mat[i][j] = min(dist_mat[i-1][j] + 1, # insert
                            dist_mat[i][j-1] + 1, # delete
                            dist_mat[i-1][j-1] + s) # substitute
    return dist_mat