#!/usr/bin/env pythondef distance(a,b): "Calculates the Levenshtein distance between a and b." n, m = len(a), len(b) if n > m: # Make sure n <= m, to use O(min(n,m)) space a,b = b,a n,m = m,n current = range(n+1) for i in range(1,m+1): previous, current = current, [i]+[0]*m for j in range(1,n+1): add, delete = previous[j]+1, current[j-1]+1 change = previous[j-1] if a[j-1] != b[i-1]: change = change + 1#; print a[j-1], b[i-1] current[j] = min(add, delete, change) return current[n]if __name__=="__main__": from sys import argv print distance(argv[1],argv[2])