Stream Of Characters

Hard
0/120
Average time to solve is 50m
profile
Contributed by
4 upvotes
Asked in companies
BarclaysAmazonApple

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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
Hint

Use brute force to check for every string formed from the current character (in the backward direction) is present in the dictionary or not.

Approaches (2)
Brute Force

The idea is to use the brute force approach for this problem. At every queried character, we will form strings in a backward direction and will simultaneously check for the string in the ‘DICTIONARY’. If we found the string, then return true. Otherwise, check till the first queried character. If still no string found in ‘DICTIONARY’, return false.
 

Note:

  1. For faster search, we can store the strings present in the ‘DICTIONARY’ in a hash set.
  2. Suppose the maximum length of the word present in the ‘DICTIONARY’ is ‘M’, then it is optimal to search till the last ‘M’ queried characters because a string of length greater than ‘M’ can never be found in the ‘DICTIONARY’.

 

Algorithm:

  • Declare three data members in the ‘private’ part of ‘CharacterStreamChecker’ class.
    • HASHSET: A hash set to store the strings present in the ‘DICTIONARY’.
    • STREAM: A string to store the stream of characters.
    • MAXLENGTH: An integer variable to store the maximum length of the string present in the ‘DICTIONARY’.
  • The ‘public’ part of ‘CharacterStreamChecker’ class contains the ‘CharacterStreamChecker’ constructor and ‘solveQuery’ function.
  • In the ‘CharacterStreamChecker’ constructor:
    • Clear the ‘HASHSET’ to remove any strings already present in the ‘HASHSET’.
    • Run a loop to traverse each string, ‘STR’ in the ‘DICTIONARY’.
      • Insert ‘STR’ in the ‘HASHSET’.
      • Declare an integer variable ‘STRLENGTH’ that will store the length of string, ‘STR’.
      • Assign the maximum of ‘MAXLENGTH’ and ‘STRLENGTH’ in the ‘MAXLENGTH’ variable.
  • In the ‘solveQuery’ function:
    • Push the queried character in ‘STREAM’.
    • Declare an integer variable ‘STREAMLENGTH’ that will store the length of string, ‘STREAM’.
    • Create a temporary string, ‘TEMP’ that will store the last queried characters to be searched in ‘DICTIONARY’.
    • Run a loop from i = STREAMLENGTH - 1 to i = max (0, STREAMLENGTH- MAXLENGTH).
      • Insert ‘STREAM[i]’ to the beginning of ‘TEMP’.
      • If HASHSET.COUNT(TEMP) > 0 that shows that ‘TEMP’ is present in the ‘HASHSET’. So, return true.
    • In the end, return false.
Time Complexity

O(N + (Q * (M ^ 2))), where ‘N’ is the number of strings in the ’DICTIONARY’, ‘Q’ is the number of queries, and ‘M’ is the maximum length of the string present in the ‘DICTIONARY’.

 

The time complexity of the ‘CharacterStreamChecker’ constructor is O(N). Since the loop inside the constructor runs ‘N’ times to insert the string in ‘HASHSET’ (Insertion in a hash set is O(1)).

Time Complexity of ‘solveQuery’ function is O((M ^ 2)) because in the worst case, the loop inside the ‘solveQuery’ function run ‘M’ times wherein each iteration of the loop, inserting the character at the beginning of the ‘temp’ string takes O(M) time. Because of ‘Q’ queries, it will result in O(Q * (M ^ 2)).

Hence, overall time complexity is O(N) + O(Q * (M ^ 2)) = O(N + (Q * (M ^ 2))).

Space Complexity

O(N + Q + M), where ‘N’ is the number of strings in the ’dictionary’, ‘Q’ is the number of queries, and ‘M’ is the maximum length of the string present in the ‘dictionary’.

 

Since the ‘HASHSET’ requires O(N) space to store the strings present in the ‘DICTIONARY’, string, ‘STREAM’ will store ‘Q’ characters at the end resulting in O(Q) space and string ‘TEMP’ will store a maximum of ‘M’ characters at any instant that will result in O(M) space.

Code Solution
(100% EXP penalty)
Stream Of Characters
Full screen
Console