2 ms·
I must be losing my mind, but I can't figure out what 3 edits would get you from rick->irkc in the final diagram. It seems like the distance is 4, not 3 (not pr
by numlocked 14y ago
I must be losing my mind, but I can't figure out what 3 edits would get you from rick->irkc in the final diagram. It seems like the distance is 4, not 3 (not problematic because the triangle inequality still holds, but it's bugging the heck out of me).
- jknighton 14y agoI trust you will find the following works, based on following the minimal branches of the Levenshtein Algorithm. "rick", "irkc": remove the final character of "irkc" (insertion) "rick", "irk": remove the final character of both strings at no cost "ric", "ir": remove the final character of both strings at a cost of 1 (substitution) "ri", "i": remove the final character of both strings at no cost "r", "": base case, cost of 1. In summary, "rick" -> "rickc" -> "ickc" -> "irkc".