Algorithm to find the correct word

Question

Imagine you are given a word samw and it is an invalid word (for the word same), and you need to find the correct word from the dictionary. The dictionary contains a list of words ordered by the frequency of the occurrence of the word with the most frequent word in the beginning.

There are the following rules on how to get the solution:

1. The wrong character should be adjacent to the correct character on the qwerty keyboard. In this case, w is adjacent to e.
2. You are given a method to get the list of adjacent characters of the keyboard

   List<Character> getAdjacent(Character char)
   

3. You are also given method to find out if two characters are adjacent

   boolean isAdjacent(Character a, Character b)
   

4. The wrong character can appear anywhere in the string and can be any number of characters also.
5. If there is more than one character matched for the wrong character, then return the string which is most frequent.

   public String autoCorrect(String wrongWord, List<String> dictionary){
   

Question: What is an efficient way to do this?

Answer 1

There are many strategies, and which is best will likely depend on a number of details not listed in the question.

For short words, the most efficient solution is to precompute everything. For each word in the dictionary, compute all possible words that can be obtained from it. Store these in a giant hashtable. If a word can be obtained in multiple ways, keep only the way with highest frequency. Then, finding the correction for a new word is as simple as looking it up in the hashtable.

For long words, one approach would be to consider only the first K letters of the word (for some K) and ignore the remaining letters, and then use the precomputation method above. The hash table will have to list all ways to complete the first K letters to a full word. You would choose K to balance off the space needed for the hashtable and time needed for the precomputation, vs the time to correct a word.

Other strategies you could consider: (1) iterate through the dictionary in decreasing order of frequency, check whether it matches the input word; (2) generate all possible variants of the input word (by all possible combinations of replacing each letter by some adjacent letter or leaving it unchanged), look each up in the dictionary, and keep the highest-frequency match; (3) use locality-sensitive hashing to find all matches in the dictionary, and keep the highest-frequency one. I suspect precomputation may be better than all of these in practice, though.

Answer 2

Some programs (e.g. git) propose possible corrections for a mistyped command (there are a few dozen). Perhaps check how they do it.