4Clojure hard题目-101

池塘仙人 发布于 2012/11/19 23:58
阅读 379
收藏 0

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!
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
(=(__[1234][02345])2)
test not run
(=(__'(🅰b:c:d)'(🅰d))2)
test not run
(=(__"ttttattttctg""tcaaccctaccat")10)
test not run
(=(__"gaattctaatctc""caaacaaaaaattt")9)
解题之前顺便发表一些感慨,有时候一些问题并不是很难,但是走错方向的话,想解出来就要千百倍的时间。


分析这个题目,先找出一些很显然的事实:

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

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

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

现在,来说一个看完答案后会很显然的事实,但是它实际上需要发现细节中一个容易被忽略的关键点才能推理出的结论

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

一看,这好像没什么玄妙,于是我问;为什么可以这样缩减规模?有可能得到这样的一个回答:难道有问题?这不正好覆盖了所有可能的情况么?这里的确没问题,关键点就是插入,删除可以在任意的位置,而如果题目的要求是只能在头或尾进行插入删除,那么上面3种缩减规模的方法,只有同时取是合法的,因为这是替换,其他两种其实是在内部插入删除。

剩下的就没什么了,实现及其简单

(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))))))

加载中
返回顶部
顶部