0

Stream Of Characters

Difficulty: HARD
Avg. time to solve
50 min
Success Rate
50%

Problem Statement
Suggest Edit

You are given a list, ‘DICTIONARY[]’ containing a list of words and a stream of characters (queries). Your task is to choose a suitable data structure to implement ‘CharacterStreamChecker’ class described as follows:

1) ‘CharacterStreamChecker(dictionary)’: Constructor to initialize the data structure with given words present in ‘DICTIONARY[]’.

2) ‘solveQuery(character)’: Function to check whether the string formed by last ‘C’ (C >= 1) queried characters (in order from oldest to newest, including the character just queried) is present in the ‘DICTIONARY[]’. If yes, return true. Otherwise, return false.

Note :

The ‘DICTIONARY[]’ contains only distinct strings.

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 third line of each test case contains an integer ‘Q’ representing the number of queries (or characters in the stream).

The last line of each test case contains ‘Q’ space-separated characters.

Output Format :

For each query in a test case, return true if the string formed by the last ‘C’ characters (C >= 1) is present in the ‘DICTIONARY[]’. Otherwise, return false.

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 <= 200
1 <= |DICTIONARY[i]| <= 200
1 <= Q <= 400
‘DICTIONARY[i]’ and ‘QUERY’ contains only lowercase english letters.

Time limit: 1 second
Sample Input 1 :
2
4
i am a ninja
9
a a m n i n j a m
3
mn p qrs 
7
m n o p q r s
Sample Output 1 :
true true true false true false false true true
false true false true false false true
Explanation of Sample Output 1 :
Test Case 1 :  
Stream: ‘a’. String “a” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘a’, ‘a’. String “a” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘a’, ‘a’, ‘m’. String “am” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘a’, ‘a’, ‘m’, ‘n’. No string out of “n”, “mn”, “amn” and “aamn” is present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘a’, ‘a’, ‘m’, ‘n’, ‘i’. String “i” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘a’, ‘a’, ‘m’, ‘n’, ‘i’, ‘n’. No string out of “n”, “in”, “nin”, “mnin”, “amnin” and “aamnin” is present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘a’, ‘a’, ‘m’, ‘n’, ‘i’, ‘n’, ‘j’. No string out of “j”, “nj”, “inj”, “ninj”, “mninj”, “amninj” and “aamninj” is present in the ‘DICTIONARY’. Therefore, the output is false.
 Stream: ‘a’, ‘a’, ‘m’, ‘n’, ‘i’, ‘n’, ‘j’, ‘a’. String “ninja” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘a’, ‘a’, ‘m’, ‘n’, ‘i’, ‘n’, ‘j’, ‘a’, ‘m’. String “am” is present in the ‘DICTIONARY’. Therefore, the output is true.


Test Case 2 : 
Stream: ‘m’. String “m” is not present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘m’, ‘n’. String “mn” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘m’, ‘n’, ‘o’. No string out of “o”, “no”, and “mno” is present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘m’, ‘n’, ‘o’, ‘p’. String “p” is present in the ‘DICTIONARY’. Therefore, the output is true.
Stream: ‘m’, ‘n’, ‘o’, ‘p’, ‘q’. No string out of “q”, “pq”, “opq”, “nopq” and “mnopq” is present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’. No string out of “r”, “qr”, “pqr”, “opqr”, “nopqr” and “mnopqr” is present in the ‘DICTIONARY’. Therefore, the output is false.
Stream: ‘m’, ‘n’, ‘o’, ‘p’, ‘q’, ‘r’, ‘s’. String “qrs” is present in the ‘DICTIONARY’. Therefore, the output is true.
Sample Input 2 :
2
5
mnn nn nnnn nmmmm nmn
7
n n n m n m n
4
a aa ab abc
5
c a b c a
Sample Output 2 :
false true true false true false true
false true true true true
Reset Code
Full screen
copy-code
Console