Skip to content

Instantly share code, notes, and snippets.

@mailpraveens

mailpraveens/levenshteinDistance.py

Created March 21, 2014 08:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mailpraveens/9681672 to your computer and use it in GitHub Desktop.
Save mailpraveens/9681672 to your computer and use it in GitHub Desktop.
Download ZIP
Recursive program to find the levenshtein distance between two strings
Raw
levenshteinDistance.py
def calculateLevenSteninDistance(a,b):
if not a: return len(b)
if not b: return len(a)
return min(calculateLevenSteninDistance(a[1:], b[1:])+(a[0] != b[0]), calculateLevenSteninDistance(a[1:], b)+1, calculateLevenSteninDistance(a, b[1:])+1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment