Skip to content

Instantly share code, notes, and snippets.

@turadg
Last active December 15, 2015 12:09
Show Gist options
  • Save turadg/5258276 to your computer and use it in GitHub Desktop.
Save turadg/5258276 to your computer and use it in GitHub Desktop.
Underscore mixin for Levenshtein distance of two strings Adapted from [Levenshtein.coffee](https://raw.github.com/phstc/levenshtein/master/src/Levenshtein.coffee) by @phstc (http://coffeescriptcookbook.com/chapters/strings/matching-strings was broken)
# usage _.levenshteinDistance("PART", "PARTY") or _("PART").levenshteinDistance("PARTY")
_.mixin
levenshtein : (str1, str2) ->
return str2.length if str1.length == 0
distance = []
for i in [0..str1.length]
distance[i] = []
distance[i][0] = i
for j in [0..str2.length]
distance[0][j] = j
for i in [1..str1.length]
for j in [1..str2.length]
deletion = distance[i - 1][j] + 1
insertion = distance[i][j - 1] + 1
substitutionCost = if (str1.charAt(i - 1) == str2.charAt(j - 1)) then 0 else 1
substitution = distance[i - 1][j - 1] + substitutionCost
distance[i][j] = Math.min(Math.min(deletion, insertion), substitution)
distance[str1.length][str2.length]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment