#101
Levenshtein Distance
 

Difficulty:Hard
Topics:seqs


Given two sequences x and y, calculate the Levenshtein distance of x and y, i. e. the minimum number of edits needed to transform x into y. The allowed edits are:

- insert a single item
- delete a single item
- replace a single item with another item

WARNING: Some of the test cases may timeout if you write an inefficient solution!
test not run
(= (__ "kitten" "sitting") 3)
test not run
(= (__ "closure" "clojure") (__ "clojure" "closure") 1)
test not run
(= (__ "xyx" "xyyyx") 2)
test not run
(= (__ "" "123456") 6)
test not run
(= (__ "Clojure" "Clojure") (__ "" "") (__ [] []) 0)
test not run
(= (__ [1 2 3 4] [0 2 3 4 5]) 2)
test not run
(= (__ '(:a :b :c :d) '(:a :d)) 2)
test not run
(= (__ "ttttattttctg" "tcaaccctaccat") 10)
test not run
(= (__ "gaattctaatctc" "caaacaaaaaattt") 9)


Code which fills in the blank: