你想要匹配兩個或多個字符串。
計算把一個字符串轉換成另一個字符串所需的編輯距離或操作數。
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)結尾處對回收數組的優(yōu)化在這里主要是為了演示 coffeescript 中交換兩個變量的語法。