#!/usr/bin/env python
# coding: utf-8

# In[ ]:





# In[1]:


import numpy as np


# In[116]:


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]


# In[117]:


s = "intention"
t = "execution"


# In[118]:


min_edit_distance(s, t)


# In[ ]:





# In[ ]: