How many typos?

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

Question was closed 2015-11-24T18:52:45.240

Can you provide a list of english words? – cat – 2015-11-24T18:07:20.453

Because I know I can use /usr/share/dict/words but 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

No answers