A typo is said to have occurred if:
- A character is missing.
- A character is extra.
- A character is replaced with another wrong character.
For the purpose of this challenge, only lowercase characters and spaces are used.
Input will be a dictionary of words, followed by one line of input. You need to find the (minimum) number of typos in it.
Sample data
For all testcases, I've assumed the dictionary to be:
heart hearth heard heaves aves he art ear
Input 1
heart heard
Output 1
0
Input 2
he art
Output 2
0
Input 3
kill us
Output 3
6
(1 to delete the space, and 5 more to change the word to hearth)
Input 4
heave art
Output 4
1
Input 5
earth artear
Output 5
2
Shortest code wins.
Please let me know of any other ambiguous testcases. I will add them here as well.
P.S.
Someone flagged this as a duplicate of Find the minimum edit distance between two strings
It is not a duplicate, in fact, my challenge is much harder. The main reasons being that:
- Substitutions are counted only as one typo in my Q, not two.
- The space is also counted as a character, and at the same time behaves like a word-separator.
/usr/share/dict/wordsbut that file is like, a megabyte \$\endgroup\$