https://www.4clojure.com/problem/101



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!

<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "kitten" "sitting") 3)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "closure" "clojure") (__ "clojure" "closure") 1)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "xyx" "xyyyx") 2)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "" "123456") 6)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "Clojure" "Clojure") (__ "" "") (__ [] []) 0)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ [1 2 3 4] [0 2 3 4 5]) 2)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ '(:a :b :c :d) '(:a :d)) 2)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "ttttattttctg" "tcaaccctaccat") 10)
<textarea wrap="off" autocorrect="off" autocapitalize="off" style=" absolute; padding-top: 0px; padding-left: 0px; width: 1px; height: 1em; outline: none !important;"></textarea>
(= (__ "gaattctaatctc" "caaacaaaaaattt") 9)

내 해답은 메모 테크닉 + 리커젼이었네 ㅋㅋ