> In information theory and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (i.e. insertions, deletions or substitutions) required to change one word into the other.

(http://en.wikipedia.org/wiki/Levenshtein_distance)


Your task is to implement a function which calculates the Levenshtein distance for two arbitrary strings.

Difficulty: introductory

Starter code:

def levenshtein(a,b):
	

Solutions:
def levenshtein(a,b):
    d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]

    d[0][:] = list(range(len(b)+1))
    for i in range(1, len(a) + 1):
        d[i][0] = i

    for i, x in enumerate(a):
        for j, y in enumerate(b):
            d[i+1][j+1] = min(1 + d[i][j+1], 1 + d[i+1][j], d[i][j] + (1 if x != y else 0))

    return d[-1][-1]



def levenshtein(s, t):
    v = range(len(t)+1)
    for i, si in enumerate(s):
        w = [i+1]
        for j, tj in enumerate(t):
            w.append(min(w[j]+1, v[j+1]+1, v[j]+(si!=tj)))
        v = w
    return w[-1]

def levenshtein(a,b):
    if len(a) == 0:
        return len(b)
    if len(b) == 0:
        return len(a)  
    if a[0] == b[0]:
        dist = 0
    else:
        dist = 1
    
    return min(
        levenshtein(a[1:], b) + 1,
        levenshtein(a, b[1:]) + 1,
        levenshtein(a[1:], b[1:]) + dist
    )


def levenshtein(a,b):
    def recurse(i, j):
        if i >= len(a) or j >= len(b):
            return abs(i - len(a)) + abs(j - len(b))
        if a[i] == b[j]:
            return recurse(i+1, j + 1)
        else:
            return 1 + min(recurse(i + 1, j), recurse(i, j + 1), recurse(i + 1, j + 1))
    return recurse(0,0)

def levenshtein(a,b):
    import numpy as np
    size_x = len(a) + 1
    size_y = len(b) + 1
    matrix = np.empty ((size_x, size_y)) 
    matrix[:,0] = list(range(size_x))
    matrix[0,:] = list(range(size_y))

    for x in range(1, size_x):
        for y in range(1, size_y):
            if a[x-1] == b[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    return (int(matrix.item((size_x-1,size_y-1))))


import numpy as np

def levenshtein(s,t):
    #create a matrix.
    m, n = len(s) , len(t)
    table = np.zeros((m, n), dtype=int)
    # first column
    for i in range(m):
        for j in range(n):
            # for first column.
            if j == 0:
                if i == 0:
                    if s[i] == t[j]:
                        table[i][j] = 0
                    else:
                        table[i][j] = 1
                if i > 0:                    
                    if s[i] == t[j]:                    
                        table[i][j] = table[i - 1][j]
                    else:                   
                        table[i][j] = table[i - 1][j] + 1
            else:
                # and first line.
                if i == 0:
                    if s[i] == t[j]:
                        table[i][j] =  table[i][j - 1]
                    else:
                        if j > 0:                            
                            table[i][j] = table[i][j - 1] + 1
                else:
                    # for others
                    if s[i] == t[j]:
                        table[i][j] =  table[i - 1][j - 1]
                    else:
                        table[i][j] = min(table[i][j - 1], table[i -1][j],table[i - 1][j - 1]) + 1 
    print(table)
    return table[-1][-1]