levenshtein.clj

(defn lev [s t]
  "Calculates Levenshtein distance for S and T.
  Time complexity is O(|s|*|t|); space complexity is O(|s|).
  Uses the swapping two-row method to avoid exponential time, see
  https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_two_matrix_rows"
  (let [s-array  (char-array s)
        t-array  (char-array t)
        s-length (count s-array)
        t-length (count t-array)]
    (loop [i  0
           v0 (int-array (inc s-length) (range))
           v1 (int-array (inc s-length))]
      (aset-int v1 0 (inc i))
      (loop [j 0]
        (aset-int v1 (inc j) 
                  (min (inc (aget v0 (inc j))) 
                       (inc (aget v1 j)) 
                       ((if (= (aget s-array i) (aget t-array j)) 
                          identity inc) 
                        (aget v0 j))))
        (if (< j (dec s-length)) 
          (recur (inc j))))
      (if (< i (dec t-length))
        (recur (inc i) v1 v0)
        (aget v1 s-length)))))