0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I'm not sure the problem statement well-defined yet. If there can be any number of wrong characters, then 'samw' could also match 'wane'. Do you really mean that out of all matches, the only thing that matters is the frequency of the matching word? Or does the number of characters you need to change also matter? If so, how do you combine those two factors into a single measure of which solution you want? $\endgroup$ – D.W. Feb 4 at 23:46
  • $\begingroup$ @D.W. you are correct, the word could be anything. 'Same' is just an example i gave. $\endgroup$ – Zeus Feb 5 at 1:56
  • $\begingroup$ I see, we want the frequency to be the priority over the number of matches. $\endgroup$ – Zeus Feb 5 at 3:02
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.