## 4Clojure hard题目－101

4Clojure是一个面向clojure初学者的在线答题网站，问题从易到难，一步步辅助初学者深入了解clojure

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!
 (=(__"kitten""sitting")3)
 (=(__"closure""clojure")(__"clojure""closure")1)
 (=(__"xyx""xyyyx")2)
 (=(__"""123456")6)
 (=(__"Clojure""Clojure")(__"""")(__[][])0)
 (=(__[1234][02345])2)
 (=(__'(🅰b:c:d)'(🅰d))2)
 (=(__"ttttattttctg""tcaaccctaccat")10)
 (=(__"gaattctaatctc""caaacaaaaaattt")9)

1、如果一个参数长度是0，那么他们的距离就是另一个参数的长度

2、如果两个参数的头相同，那么用剩余部分递归调用会得到相同的结果

3、向一个参数插入一个值和从另一个参数删除一个值等价

4、当2不成立时，该问题的结果就是1+min（同时取a、b的剩余部分递归调用会得到的结果；原本的a、剩余的b递归调用会得到的结果；原本的b、剩余的a递归调用会得到的结果

(fn f [a b]
(cond (empty? a) (count b)
(empty? b) (count a)
(= (first a) (first b)) (recur (rest a) (rest b))
:else (inc (min (f (rest a) b) (f a (rest b)) (f (rest a) (rest b))))))