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

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