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:
- The wrong character should be adjacent to the correct character on the qwerty keyboard. In this case,
w
is adjacent toe
. - You are given a method to get the list of adjacent characters of the keyboard
List<Character> getAdjacent(Character char)
- You are also given method to find out if two characters are adjacent
boolean isAdjacent(Character a, Character b)
- The wrong character can appear anywhere in the string and can be any number of characters also.
- 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?