Did this early in the morning and was groggy and somehow allowed myself to type “famous” like that.
Thought it was sorta funny and that some of you might think the same.
17 Likes
Woah, WK must have a pretty lax Levenshtein distance algo if that was accepted.
But yes, we are all thankful for the typo-leniency 
1 Like
For a 6 letter answer “Famous”, the maximum Levenshtein distance allowed is 2. By the official Levenshtein algorithm, “faomu” should have been rejected. Which makes me think WK might be using Damerau-Levenshtein, which is a little more forgiving, since it considers swapping two letters a single edit action. So “faomu” -> “famou” -> “famous” in two steps.
Looking at the javascript, it does indeed look more like Damerau-Levenshtein than plain old Levenshtein. So I suspect it’s deliberate that this is considered acceptable.
4 Likes
Followup: so, I dug a little deeper since that is just the kind of geek I am…
To be precise, WK is not using the real Levenshtein or Damerau-Levenshtein, even though their code calls it Levenshtein. What they are using is Optimal String Alignment, which kind-of, sort-of is halfway between Levenshtein and Damerau-Levenshtein, and it will allow for transpositions.
This algorithm is commonly mistaken for the real thing, but it’s not. It’s often used by developers thinking it’s Levenshtein, though. But the advantage is that it’s very efficient and ‘close enough’ for most practical purposes.
And it is deliberately designed to allow for “faomu” -> “famous” in two steps.
2 Likes
nice sleuthing!
1 Like
This topic was automatically closed 365 days after the last reply. New replies are no longer allowed.