(levenshtein-distance s t)
The the minimum number of single-element edits needed to
transform s in to t.
Source
(defn levenshtein-distance
"The the minimum number of single-element edits needed to
transform s in to t."
[s t]
(let [f (fn [f s t]
(cond
(empty? s) (count t)
(empty? t) (count s)
:else (let [cost (if (= (first s) (first t))
0
1)]
(min (inc (f f (rest s) t))
(inc (f f s (rest t)))
(+ cost (f f (rest s) (rest t)))))))
g (memoize f)]
(g g s t)))