# algorithm – Edit Distance in Python

## algorithm – 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]
```

#### algorithm – Edit Distance in Python

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))