3
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.
ghosts_in_the_code
Posted 2015-11-24T18:05:34.587
Reputation: 2 907
Can you provide a list of english words? – cat – 2015-11-24T18:07:20.453
Because I know I can use
/usr/share/dict/wordsbut that file is like, a megabyte – cat – 2015-11-24T18:08:24.523@flawr Please see my clarification on why this is not a dup. – ghosts_in_the_code – 2015-11-24T18:13:35.393
1Scoring a substitution as 1 vs 2 involves literally no more than changing a single character from 1 to 2 in some (most?) of the answers to the older question, so I have no idea why you think that makes it "*much harder*". I'm not sure I understand what you mean with the other reason. – Peter Taylor – 2015-11-24T18:59:21.953