CoffeeScript 匹配字符串

匹配字符串

問題

你想要匹配兩個或多個字符串。

解決方案

計算把一個字符串轉換成另一個字符串所需的編輯距離或操作數(shù)。

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]

討論

可以使用赫斯伯格（Hirschberg）或瓦格納菲舍爾（Wagner–Fischer）的算法來計算來文史特（Levenshtein）距離。這個例子用的是瓦格納菲舍爾算法。

這個版本的文史特算法和內存呈線性關系，和時間呈二次方關系。

在這里我們使用str.charAt i這種表示法而不用str[i]這種方式，是因為后者在某些瀏覽器（如IE7）中不支持。

起初，"by 1"在兩次循環(huán)中看起來似乎是沒用的。它在這里是用來避免一個coffeescript [i..j]語法的常見錯誤。如果str1或str2為空字符串，那么[1..l1]或[1..l2]將會返回[1,0]。添加了"by 1"的循環(huán)也能編譯出更加簡潔高效的javascript 。

最后，循環(huán)結尾處對回收數(shù)組的優(yōu)化在這里主要是為了演示coffeescript中交換兩個變量的語法。