# Algorithm to find the correct word

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?

• 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?
– D.W.
Commented Feb 4, 2020 at 23:46
• @D.W. you are correct, the word could be anything. 'Same' is just an example i gave.
– Zeus
Commented Feb 5, 2020 at 1:56
• I see, we want the frequency to be the priority over the number of matches.
– Zeus
Commented Feb 5, 2020 at 3:02