Auto Suggestion

Hard
0/120
Average time to solve is 60m
profile
Contributed by
5 upvotes
Asked in companies
AmazonMicrosoftGoldman Sachs

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
4 
abc ab aa a
3
abc
3
na bw a
3
abc
Sample Output 1:
a aa ab
ab abc 
abc
a
Explanation for Sample Input 1:
In the first test case, after Bob types ‘a’, the program suggests ‘a aa ab’. After typing ‘ab’ , the program suggests ‘ab abc’, and after typing ‘abc’ the program suggests ‘abc’.  
In the second test case, after Bob types ‘a’, the program suggests ‘a’ but after typing ‘ab’ and ‘abc’, the program suggests noting.
Sample Input 2:
2
2 
cn cnn
1 
c
1
roll
4
roll
Sample Output 2:
cn cnn 
roll
roll
roll
roll
Hint

How to optimise the searching process?

Approaches (3)
Can sorting help?

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]’
  • Return ‘ans’
Time Complexity

O(N * log(N) + L * N), where ‘N’ is the number of strings and ‘L’ is the length of the string Bob is going to type.


 

Assuming that comparing two strings takes O(1), sorting the array of strings will take O(N * log(N)) and searching each time will take O(N) time. So total time complexity becomes O(N * log(N) + N * L).


 

Space Complexity

O(1)

We are using constant extra space.


 

Code Solution
(100% EXP penalty)
Auto Suggestion
Full screen
Console