edit.py

def edit_distance(a, b):
    m,n=len(a),len(b)

    ins_cost = 1
    del_cost = 1

    cost = {}
    for i in range(m+1): 
      cost[i,0]=i*ins_cost
    for j in range(n+1): 
      cost[0,j]=j*del_cost
    for i in range(1, m+1):
        for j in range(1, n+1):
            sub_cost = 0 if a[i-1] == b[j-1] else 1
            cost[i,j] = min(cost[i, j-1]+del_cost, 
                            cost[i-1, j]+ins_cost, 
                            cost[i-1, j-1]+sub_cost)

    return cost[m,n]