Last Updated: 27 Mar, 2021
Spell Checker
Hard
Asked in companies
You are given a list of strings, ‘DICTIONARY[]’ that represents the correct spelling of words and a query string ‘QUERY’ that may have incorrect spelling. You have to check whether the spelling of the string ‘QUERY’ is correct or not. If not, then return the list of suggestions from the list ‘DICTIONARY’. Otherwise, return an empty list which will be internally interpreted as the correct string.
Note:
1) The suggested correct strings for the string ‘QUERY’ will be all those strings present in the ‘DICTIONARY[]’ that have the prefix same as the longest prefix of string ‘QUERY’.
2) The ‘DICTIONARY[]’ contains only distinct strings.
For example:
Given 'DICTIONARY[]' = {“ninja”, “ninjas”, “nineteen”, “ninny”} and query = “ninjk”. Since “ninjk” is not present in the ‘DICTIONARY[]’, it is an incorrect string. The suggested current spellings for “ninjk” are “ninja” and “ninjas”. It is because “ninj” is the longest prefix of “ninjk” which is present as the prefix in ‘DICTIONARY’.
Input Format
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains an integer ‘N’ representing the number of strings in the list, ‘DICTIONARY[].’
The second line of each test case contains ‘N’ space separated strings present in the list, ‘DICTIONARY[]’.
The last line of each test case contains the ‘QUERY’ string.
Output Format:
For each test case, return a list of strings containing all suggested correct spellings from the list, ‘DICTIONARY[]’, if the spelling of the ‘query’ string is incorrect. Otherwise, return an empty list that will be internally interpreted as the correct string and will print “CORRECT”.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 100
1 <= |DICTIONARY[i]| <= 100
1 <= |QUERY| <= 100
‘DICTIONARY[i]’ and ‘QUERY’ contains only lowercase english letters.
Where ‘|DICTIONARY[i]|’ is the length of the string in the list ‘DICTIONARY' and ‘|QUERY|’ is the length of the ‘QUERY’ string.
Time limit: 1 sec
Approaches
The entire problem is reduced to a prefix matching problem when the ‘QUERY' string is not present in the ‘DICTIONARY’. The idea is to use trie data structure as it is the most suitable and fastest data structure in prefix matching.
First, we will build a trie and insert all the strings of ‘DICTIONARY’ in the trie. Then, we will traverse the string, ‘QUERY and match it with the character present in the trie. At any moment, the character does not match, the substring before that character will be the longest prefix of string, ‘QUERY. So, we will store all the strings from the ‘DICTIONARY’ that matches with the longest prefix of string, ‘QUERY, in a list and then return the list.
If the string, ‘QUERY matches completely with any string in the trie. It suggests that ‘QUERY is spelt correctly. So, we will return an empty list.
Structure of ‘Trie’:
- A pointer array, ‘CHILD’ of type ‘Trie’ of size 26 to point to the string’s next character.
- A boolean variable, ‘isEnd’, to mark the end of the string.
- Constructor of ‘Trie’ initializes all the elements of ‘CHILD’ by NULL and ‘isEnd’ by false.
The steps are as follows:
- Create a node ‘ROOT' of type ‘Trie’.
- Run a loop from ‘i’ = 0 to the size of ‘DICTIONARY’:
- Call the ‘INSERT’ function and pass ‘ROOT’ and string at ‘i’th position in the dictionary to insert the string in the ‘Trie’.
- Declare a vector of string, ‘RESULT’ to store all possible spelling suggestions.
- Run a loop from ‘i’ = 0 to the length of ‘QUERY':
- Declare an integer variable, ‘INDEX’ and assign ‘QUERY[i]’ - ‘a’, that stores the index of the character in the ‘Trie’.
- If 'ROOT'->‘CHILD’[index] == NULL that shows that character at index ‘i’ in ‘QUERY' is not present in the ‘Trie’.
- Declare a string, ‘prefixQuery’, and store the substring of ‘QUERY' up to index ‘i’ - 1 in ‘prefixQuery’.
- Pass ‘ROOT’, ‘prefixQuery’ and ‘RESULT’ to the ‘findSuggestions’ function to store all the suggested correct spellings starting with prefix ‘prefixQuery’ in the ‘RESULT’.
- Return ‘RESULT’.
- If 'ROOT'->‘CHILD’[index] == NULL that shows that character at index ‘i’ in ‘QUERY' is not present in the ‘Trie’.
- Declare an integer variable, ‘INDEX’ and assign ‘QUERY[i]’ - ‘a’, that stores the index of the character in the ‘Trie’.
- If ‘ROOT’->isEnd = true, that shows that the string, ‘QUERY' is present in the ‘Trie’ (i.e., ‘query’ is present in the ‘dictionary’). So, ‘QUERY is correctly spelt. Therefore, return ‘RESULT’, i.e., an empty list.
- Otherwise, the longest prefix of ‘QUERY' to be searched in ‘DICTIONARY’ is ‘QUERY’ itself. So, pass ‘ROOT’, ‘QUERY’ and ‘RESULT’ to the ‘findSuggestions’ function to store all the suggested correct spellings starting with the prefix ‘QUERY' in the ‘RESULT’.
- Return the ‘RESULT’.
Description of ‘INSERT’ function:
This function will take two parameters :
- ‘ROOT’: A pointer to the root node of the ‘Trie’.
- ‘STR’: A string variable to store the string from ‘DICTIONARY’.
void insert(‘ROOT’, ‘STR’):
- Declare an integer variable, ‘i’ and initialize with 0 to traverse the string, ‘STR’.
- Run a loop while i < length of ‘STR’
- Declare an integer variable, ‘INDEX’ and assign ‘STR[i]’ - ‘a’, that stores the index of the current character of ‘STR’ in the ‘Trie’.
- If ‘ROOT’->‘CHILD’[INDEX] == NULL that shows that the current character of ‘STR’ is not present in the ‘Trie’. So, create a new node and update ‘‘ROOT’->‘CHILD’[i]’ by address of the new node.
- Update ‘ROOT’ by ‘‘ROOT’->‘CHILD’[i]’.
- Increment ‘i’ by 1.
- Declare an integer variable, ‘INDEX’ and assign ‘STR[i]’ - ‘a’, that stores the index of the current character of ‘STR’ in the ‘Trie’.
- Update ‘ROOT’->'isEnd' by true.
Description of ‘findSuggestions’ function:
This function will take three parameters :
- ‘ROOT’: A pointer to the root node of the ‘Trie’.
- ‘possibleAnswer’: A string variable to store the possible answer prefixed with the longest prefix of the string, ‘QUERY’.
- ‘RES’: A vector of string to store all the suggested correct spellings.
void findSuggestions(‘ROOT’, ‘possibleAnswer', ‘RES’):
- If ‘ROOT’->'isEnd' = true, that shows we have reached the end of the string. So, insert ‘possibleAnswer’ in ‘RES’ and return.
- Otherwise, run a loop from ‘i’ = 0 to 26.
- If ‘ROOT’->‘CHILD’[i] != NULL that shows that the character at index ‘i’ in ‘Trie’ is present.
- Insert the character at the end of the string, ‘possibleAnswer’.
- Recursively call ‘findSuggestions’ function with updated ‘possibleAnswer’.
- Pop the last character of the string, ‘possibleAnswer’.
- If ‘ROOT’->‘CHILD’[i] != NULL that shows that the character at index ‘i’ in ‘Trie’ is present.