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,"Both Levenshtein Distance Algorithm implementations are included on the demo page.
" c[i,j] = min(x,y,z) return c[n,m]