You want to match two or more strings.
Calculate the edit distance, or number of operations required to transform one string into the other.
levenshtein = (str1, str2) -> l1 = str1.length l2 = str2.length prevDist = [0..l2] nextDist = [0..l2] for i in [1..l1] by 1 nextDist = i for j in [1..l2] by 1 if (str1.charAt i-1) == (str2.charAt j-1) nextDist[j] = prevDist[j-1] else nextDist[j] = 1 + Math.min prevDist[j], nextDist[j-1], prevDist[j-1] [prevDist,nextDist]=[nextDist, prevDist] prevDist[l2]
You can use either Hirschberg or Wagner–Fischer’s algorithm to calculate a Levenshtein distance. This example uses Wagner–Fischer’s algorithm.
This version of Levenshtein algorithm is linear in memory, quadratic in time.
str.charAt i is preferred here to stri because the latter syntax is not supported by some browsers (e.g. IE7).
Finally the optimization of recycling of arrays at the end of the loops is mainly here to demonstrate the syntax of coffeescript for swapping two variables.