import numpy as np
def min_edit_distance(source, target):
n = len(source)
m = len(target)
D = np.zeros((n+1, m+1))
D[:, 0] = range(n+1)
D[0, :] = range(m+1)
for i in range(1, n+1):
for j in range(1, m+1):
dc = D[i-1, j] + 1
ic = D[i, j-1] + 1
if source[i-1] == target[j-1]:
sc = D[i-1, j-1]
else:
sc = D[i-1, j-1] + 2
D[i, j] = min(dc, ic, sc)
print(D)
return D[n, m]
s = "intention"
t = "execution"
min_edit_distance(s, t)
[[ 0. 1. 2. 3. 4. 5. 6. 7. 8. 9.] [ 1. 2. 3. 4. 5. 6. 7. 6. 7. 8.] [ 2. 3. 4. 5. 6. 7. 8. 7. 8. 7.] [ 3. 4. 5. 6. 7. 8. 7. 8. 9. 8.] [ 4. 3. 4. 5. 6. 7. 8. 9. 10. 9.] [ 5. 4. 5. 6. 7. 8. 9. 10. 11. 10.] [ 6. 5. 6. 7. 8. 9. 8. 9. 10. 11.] [ 7. 6. 7. 8. 9. 10. 9. 8. 9. 10.] [ 8. 7. 8. 9. 10. 11. 10. 9. 8. 9.] [ 9. 8. 9. 10. 11. 12. 11. 10. 9. 8.]]
8.0