Anonymous user
Levenshtein distance/Alignment: Difference between revisions
Racket
(→{{header|Perl}}: put everything in one array for a shorter code) |
(Racket) |
||
Line 83:
<pre>ro-settac-o-de
raisethysword-</pre>
=={{header|Racket}}==
This solution only computes the distance.
See http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html
for a discussion of the code.
<lang racket>
#lang racket
(define (memoize f)
(local ([define table (make-hash)])
(lambda args
(dict-ref! table args (λ () (apply f args))))))
(define levenshtein
(memoize
(lambda (s t)
(cond
[(and (empty? s) (empty? t)) 0]
[(empty? s) (length t)]
[(empty? t) (length s)]
[else
(if (equal? (first s) (first t))
(levenshtein (rest s) (rest t))
(min (add1 (levenshtein (rest s) t))
(add1 (levenshtein s (rest t)))
(add1 (levenshtein (rest s) (rest t)))))]))))
</lang>
(levenshtein (string->list "rosettacode")
(string->list "raisethysword"))
| |||