Edit Distance in Python

The thing you are looking at is called an edit distance and here is a nice explanation on wiki. There are a lot of ways how to define a distance between the two words and the one that you want is called Levenshtein distance and here is a DP (dynamic programming) implementation in python.

def levenshteinDistance(s1, s2):    if len(s1) > len(s2):        s1, s2 = s2, s1    distances = range(len(s1) + 1)    for i2, c2 in enumerate(s2):        distances_ = [i2+1]        for i1, c1 in enumerate(s1):            if c1 == c2:                distances_.append(distances[i1])            else:                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))        distances = distances_    return distances[-1]

And a couple of more implementations are here.

difflib in the standard library has various utilities for sequence matching, including the get_close_matches method that you could use. It uses an algorithm adapted from Ratcliff and Obershelp.

From the docs

>>> from difflib import get_close_matches>>> get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])['apple', 'ape']

Here is my version for Levenshtein distance

def edit_distance(s1, s2):    m=len(s1)+1    n=len(s2)+1    tbl = {}    for i in range(m): tbl[i,0]=i    for j in range(n): tbl[0,j]=j    for i in range(1, m):        for j in range(1, n):            cost = 0 if s1[i-1] == s2[j-1] else 1            tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost)    return tbl[i,j]print(edit_distance("Helloworld", "HalloWorld"))