: last  ( addr u -- c )  1- chars + c@ ;
 
: levenshtein  ( addr1 u1 addr2 u2 -- uedits )
  dup 0= if 2drop nip exit then 2>r \ if either string is empty, difference
  dup 0= if 2drop 2r> nip exit then \ is inserting all chars from the other.
  2dup last 2r@ last =              \ last chars equal? then ignore and recur,
  if 1- 2r> 1- recurse exit then    \ else 1 edit plus least distance after:
  2dup 1- 2r@ recurse -rot          \   an insertion,
  2dup 2r@ 1- recurse -rot          \   a deletion,
  1- 2r> 1- recurse  min min 1+ ;   \   or a substitution.
 
s" kitten"      s" sitting"       levenshtein . cr
s" rosettacode" s" raisethysword" levenshtein . cr
 

OiBsYXN0ICAoIGFkZHIgdSAtLSBjICkgIDEtIGNoYXJzICsgY0AgOwoKOiBsZXZlbnNodGVpbiAgKCBhZGRyMSB1MSBhZGRyMiB1MiAtLSB1ZWRpdHMgKQogIGR1cCAwPSBpZiAyZHJvcCBuaXAgZXhpdCB0aGVuIDI+ciBcIGlmIGVpdGhlciBzdHJpbmcgaXMgZW1wdHksIGRpZmZlcmVuY2UKICBkdXAgMD0gaWYgMmRyb3AgMnI+IG5pcCBleGl0IHRoZW4gXCBpcyBpbnNlcnRpbmcgYWxsIGNoYXJzIGZyb20gdGhlIG90aGVyLgogIDJkdXAgbGFzdCAyckAgbGFzdCA9ICAgICAgICAgICAgICBcIGxhc3QgY2hhcnMgZXF1YWw/IHRoZW4gaWdub3JlIGFuZCByZWN1ciwKICBpZiAxLSAycj4gMS0gcmVjdXJzZSBleGl0IHRoZW4gICAgXCBlbHNlIDEgZWRpdCBwbHVzIGxlYXN0IGRpc3RhbmNlIGFmdGVyOgogIDJkdXAgMS0gMnJAIHJlY3Vyc2UgLXJvdCAgICAgICAgICBcICAgYW4gaW5zZXJ0aW9uLAogIDJkdXAgMnJAIDEtIHJlY3Vyc2UgLXJvdCAgICAgICAgICBcICAgYSBkZWxldGlvbiwKICAxLSAycj4gMS0gcmVjdXJzZSAgbWluIG1pbiAxKyA7ICAgXCAgIG9yIGEgc3Vic3RpdHV0aW9uLgoKcyIga2l0dGVuIiAgICAgIHMiIHNpdHRpbmciICAgICAgIGxldmVuc2h0ZWluIC4gY3IKcyIgcm9zZXR0YWNvZGUiIHMiIHJhaXNldGh5c3dvcmQiIGxldmVuc2h0ZWluIC4gY3IK