Check the internet for many other explanations and implementations. A particularly elegant recursive and short (but slow) version in the Python programming language (yes, it IS named after Monty Python) is given here:
def levenshtein(a, b):
if not a: return len(b)
if not b: return len(a)
return min(int(a[0] != b[0]) + levenshtein(a[1:], b[1:]), 1 + levenshtein(a[1:], b), 1 + levenshtein(a, b[1:]))
(Source: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Levenshtein_distance#Python)
A classic iterative Python implementation is this longer but faster version:
def levenshtein_iter02(a,b):
c = {}
n = len(a); m = len(b)
for i in range(0,n+1):
c[i,0] = i
for j in range(0,m+1):
c[0,j] = j
for i in range(1,n+1):
for j in range(1,m+1):
x = c[i-1,j]+1
y = c[i,j-1]+1
if a[i-1] == b[j-1]:
z = c[i-1,j-1]
else:
z = c[i-1,j-1]+1
if traceflag=='on':
print deletion,insertion, substution,"
"
c[i,j] = min(x,y,z)
return c[n,m]
Both Levenshtein Distance Algorithm implementations are included on the demo page.