Last Updated: 30 Nov, 2021
Auto Suggestion
Hard
Asked in companies
Bob had a hard time remembering the spelling of words. Alice, his best friend, decided to make a program that suggests words after every character Bob types.
Alice had an array of ‘N’ strings ‘S’ containing Bob’s most commonly used words. She decided to suggest at most three words after each character is typed. The typed word and the suggested word should have the same prefix. If there are more than 3 such words in the array, print the three lexicographically minimum words.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases.
The first line of each test case contains one integer ‘N’, denoting the number of strings in the array.
The following line contains an array ‘S’ of ‘N’ spaced strings denoting the commonly used strings by Bob.
The following line contains an integer ‘L’ denoting the length of the string Bob is going to type.
The following line contains a string ‘P’ denoting the string Bob is going to type.
Output Format:
For each test case, print ‘L’ lines containing at most three single space-separated words that the Alices program will suggest after each character of string ‘P’ is typed.
Note:
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 1000
1 <= L <= 1000
1 <= Sum of lengths of all ‘S[i]’ <= 2 * 10 ^ 4.
There are no repeated elements in the array ‘S’.
All characters in ‘S[i]’ and ‘P’ are lower-case English letters.
Time Limit: 1 sec
Approaches
We will need to ask ‘L’ questions where ‘L’ is the length of the string Bob is going to type. In each question, we will have to find 3 lexicographically minimum words which have the same prefix as that of the word typed.
If we sort all the strings, words with the same prefix will get aligned one after another lexicographically. So we will only need to find the first string that has the same prefix as the word we are searching for and take that string along with the next 2 strings if they have the same prefix.
Algorithm:
- Create a function ‘isPrefix’ that takes two strings and returns true if the first string is a prefix of the second string.
- Create a vector of vector strings ‘ans’ of size ‘L’ to store the answer.
- Declare an empty string ‘word’.
- Sort all the strings present in ‘S’.
- Run a loop ‘i’ from 0 to ‘L’ - 1
- Add ‘P[i]’ at the end of ‘word’
- Run a loop ‘j’ from 0 to ‘N’ - 1
- If ‘isPrefix(word, S[j]) is true
- Add ‘S[j]’ to ‘ans[i]’
- If ‘j’ + 1 is less than ‘N’ and ‘isPrefix(word, S[j + 1]) is true,add ‘S[j + 1]’ to ‘ans[i]’
- If ‘j’ + 2 is less than ‘N’ and ‘isPrefix(word, S[j + 2]) is true,add ‘S[j + 2]’ to ‘ans[i]’
- If ‘isPrefix(word, S[j]) is true
- Return ‘ans’
After sorting we need to find the first index that has same prefix as that of the word we are searching for. Since the array of strings is sorted, we can use binary search to find the first index with the same prefix and check the next two strings if they have the same prefix.
Algorithm:
- Create a function ‘isPrefix’ that takes two strings and returns true if the first string is a prefix of the second string.
- Create a vector of vector strings ‘ans’ of size ‘L’ to store the answer.
- Declare an empty string ‘word’.
- Sort all the strings present in ‘S’.
- Run a loop ‘i’ from 0 to ‘L’ - 1
- Add ‘S[i]’ at the end of ‘word’
- Binary search to find the lower bound of ‘word’ in the array ‘S’
- If no such index is present , continue.
- Let ‘j’ be the index of that string.
- If ‘isPrefix(word, S[j]) is true, add ‘S[j]’ to ‘ans[i]’
- If ‘j’ + 1 is less than ‘N’ and ‘isPrefix(word, S[j + 1]) is true,add ‘S[j + 1]’ to ‘ans[i]’
- If ‘j’ + 2 is less than ‘N’ and ‘isPrefix(word, S[j + 2]) is true,add ‘S[j + 2]’ to ‘ans[i]’
- Return ‘ans’
We need a data structure that allows us to search for all the words with the given prefix. We can use the trie data structure to store all the words. The question also asks for sorted results. If you look closely, a trie word is represented by its preorder traversal. It is also worth noting that a preorder traversal of a trie will always result in a sorted traversal of results. Thus all we need to do is limit the word traversal to 3.
Algorithm:
- Create a vector of vector strings ‘ans’ of size ‘L’ to store the answer.
- Declare an empty string ‘word’.
- Create a Trie from the strings in the array.
- Iterate each character of ‘P’
- Add the current character at the end of ‘word’
- After adding the current character to the prefix traverse the trie pointer to the node representing prefix.
- Now traverse the tree from curr pointer in a preorder fashion and record whenever we encounter a complete word.
- Limit the result to 3 and return dfs once reached this limit.
- Add the words to the final result.