Edit distance

In [3]:

    

import numpy as np


    

In [29]:

    

def edit_distance(x: str, y: str) -> int:
    m = len(x)
    n = len(y)
    
    e = np.zeros((m + 1, n + 1))
    
    for i in range(1, m):
        e[i, 0] = i
    for j in range(1, n):
        e[0, j] = i
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                e[i, j] = e[i - 1, j - 1]
            else:
                e[i, j] = 1 + min(
                    e[i - 1, j - 1],
                    e[i, j - 1],
                    e[i - 1, j]
                )
    return e[m, n]


    

In [30]:

    

edit_distance('exponential', 'polynomial')


    

    
Out[30]:





6.0

In [31]:

    

edit_distance('algo', 'log')


    

    
Out[31]:





3.0

In [34]:

    

edit_distance('lovely', 'volvo')


    

    
Out[34]:





5.0

In [ ]: