Levenshtein distance with only previous row tracking.

levenshtein_prev_row.clj

(defn levenshtein-distance [w1 w2]
  "Computes the levenshtein distance between two words."
  (letfn [(cell-value [ch1 ch2 prev-row acc col-idx]
            (min  (inc (nth prev-row col-idx))
                  (inc (last acc))
                  (+ (nth prev-row (dec col-idx)) (if (= ch1 ch2) 0 1))))]

    (loop [row-idx 1, max-rows (inc (count w2)), prev (range (inc (count w1)))]
      (if (= row-idx max-rows)
        (last prev)
        (let [ch2 (nth w2 (dec row-idx))
              next-prev (reduce (fn [acc i]
                                  (conj acc (cell-value (nth w1 (dec i)) ch2 prev acc i)))
                                [row-idx]
                                (range 1 (count prev)))]
          (recur (inc row-idx) max-rows, next-prev))))))