[Community Puzzle] Levenshtein distance

Puzzles
#1

Hi there, my code is failing the test for “Long words”.

Going by the puzzle’s description:

The Levenstein distance is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one string into the other.

Given an input of:

supercalifragilisticexpialidocious (Length 34)
pseudopseudohypoparathyroidism (Length 30)

I’m assuming that the first string would need 30 substitutions…

> 1. s -> p > 2. u -> s > 3. p -> e > 4. e -> u > 5. r -> d > 6. c -> o > 7. a -> p > 8. l -> s > 9. i -> e > 10. f -> u > 11. r -> d > 12. a -> o > 13. g -> h > 14. i -> y > 15. l -> p > 16. i -> o > 17. s -> p > 18. t -> a > 19. i -> r > 20. c -> a > 21. e -> t > 22. x -> h > 23. p -> y > 24. i -> r > 25. a -> o > 26. l -> i > 27. i -> d > 28. d -> i > 29. o -> s > 30. c -> m

… And the deletion of its last 4 characters (ious) in order to be equal to the second string. A total of 34 steps. This test is expecting an output of 30, so… What am I missing?

#2

You don’t have to delete the last 4 characters - you just have to delete 4 characters.
eg.
aba
can be turned into
b
by deleting the first and last (2), but your method would delete the last 2 and then switch the a -> b (3).

1 Like