21 lines
1.1 KiB
Clojure
21 lines
1.1 KiB
Clojure
(defn levenshtein [w1 w2]
|
|
(letfn [(cell-value [same-char? prev-row cur-row col-idx]
|
|
(min (inc (nth prev-row col-idx))
|
|
(inc (last cur-row))
|
|
(+ (nth prev-row (dec col-idx)) (if same-char?
|
|
0
|
|
1))))]
|
|
(loop [row-idx 1
|
|
max-rows (inc (count w2))
|
|
prev-row (range (inc (count w1)))]
|
|
(if (= row-idx max-rows)
|
|
(last prev-row)
|
|
(let [ch2 (nth w2 (dec row-idx))
|
|
next-prev-row (reduce (fn [cur-row i]
|
|
(let [same-char? (= (nth w1 (dec i)) ch2)]
|
|
(conj cur-row (cell-value same-char?
|
|
prev-row
|
|
cur-row
|
|
i))))
|
|
[row-idx] (range 1 (count prev-row)))]
|
|
(recur (inc row-idx) max-rows next-prev-row))))))
|