CoffeeScript matches strings

Match string

Problem

You want to match two or more strings.

Solution

Calculates the amount of editing distance or operation required to convert one string to another.

levenshtein = (str1, str2) ->

    l1 = str1.length
    l2 = str2.length
    prevDist = [0..l2]
    nextDist = [0..l2]

    for i in [1..l1] by 1
      nextDist[0] = 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]

Discuss

The Levenshtein distance can be calculated using the algorithms of Hirschberg or Wagner-Fischer. This example uses the Wagner Fischer algorithm.

This version of the Texter algorithm has a linear relationship with memory and a secondary relationship with time.

Here we use the notation of str.charAt i instead of str.i, because the latter is not supported in some browsers, such as IE7.

At first, "by 1" seemed useless in two loops. I t is here used to avoid a coffee script ( i. a common error in the syntax. I f str1 or str2 are empty strings, then 1..l1 or 1.l2 will return . A loop with "by 1" added also compiles a cleaner and more efficient javascript.

Finally, the optimization of the recycled array at the end of the loop is here primarily to demonstrate the syntax of exchanging two variables in coffee script.