# Edit Distance

import numpy as np

def min_ed_dist(target, source):
    target = [k for k in target]
    source = [k for k in source]
    
    sol = np.zeros((len(source),len(target)))

    sol[0] = [j for j in range(len(target))]
    sol[:,0] = [i for i in range(len(source))]
    
    for c in range(1, len(target)):
        for r in range(1, len(source)):
            if target[c] != source[r]:
                sol[r,c] = min(sol[r-1,c], sol[r,c-1], sol[r-1,c-1])+1
            else:
                sol[r,c] = sol[r-1,c-1]
    return sol

String1 = input("Enter String 1 : ")
String2 = input("Enter String 2 : ")
sol = min_ed_dist(String1,String2)
print(sol)
print("Minimum edit distance is ", sol[len(String1)-1,len(String2)-1])