Auto Suggestion

Hard

0/120

Average time to solve is 60m

Contributed by

4 upvotes

Asked in companies

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

Console