CoffeeScript 匹配字符串

匹配字符串

問題

你想要匹配兩個(gè)或多個(gè)字符串。

解決方案

計(jì)算把一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串所需的編輯距離或操作數(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）的算法來(lái)計(jì)算來(lái)文史特（Levenshtein）距離。這個(gè)例子用的是瓦格納菲舍爾算法。

這個(gè)版本的文史特算法和內(nèi)存呈線性關(guān)系，和時(shí)間呈二次方關(guān)系。

在這里我們使用str.charAt i這種表示法而不用str[i]這種方式，是因?yàn)楹笳咴谀承g覽器（如IE7）中不支持。

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

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