Stream Of Characters

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.

It is not easier to develop a solution to this problem by the usual approach. But if we look at the problem in a way to match the reverse of ‘C’ stream of characters with reversed strings present in the ‘dictionary’. Then the entire problem is reduced to a prefix matching problem. The idea is to use trie data structure as it is the most suitable and fastest data structure for prefix matching.

First, we will build a trie and insert all the strings of ‘DICTIONARY’ in reversed order in the ‘TRIE’. We will maintain a string, ‘STREAM’, that will store the stream of characters at any instant. For every queried character, search the ‘STREAM’ from the end in the ‘TRIE’. If we found a node representing the end of the word, it means that character present at that node till the queried character is a valid word present in the ‘DICTIONARY’. So, we will return true.

If not, then we have two cases:

1. We have reached the end of the ‘TRIE’. So, return false.
2. We have reached the beginning of the ‘STREAM’. If the node representing the first character of ‘STREAM’ is the end of the word. Then, return true otherwise false.

‘Trie’ Class:

• A pointer array, ‘CHILD’ of type ‘TRIE’ of size 26 to point to the string’s next character.
• A boolean variable, ‘ISND’, to mark the end of the string.
• Constructor of ‘TRIE’ initializes all the elements of ‘CHILD’ by NULL and ‘ISEND’ by false.
• Destructor of ‘TRIE’ to deallocate the memory used by ‘CHILD’ pointers.
   

Algorithm:

• Create a ‘TRIE’ class.
• Declare two data members and one member function in the ‘private’ part of ‘CharacterStreamChecker’ class.
  • STREAM: A string to store the stream of characters.
  • ROOT: Pointer to the ‘Trie’ node.
  • insert: A function to insert the reverse of string in a ‘TRIE’.
• The ‘public’ part of ‘CharacterStreamChecker’ class contains the  ‘CharacterStreamChecker’ constructor and ‘solveQuery’ function.
• In the ‘CharacterStreamChecker’ constructor:
  • Allocate memory for the ‘ROOT’ node of ‘TRIE’.
  • Run a loop to traverse each string, ‘STR’ in the ‘DICTIONARY’.
    • Call the ‘insert’ function to store the reverse of ‘STR’ in the ‘TRIE’.
• In the ‘solveQuery’ function:
  • Push the queried character in ‘STREAM’.
  • Declare a pointer of ‘TRIE’, ‘TEMPROOT’ and assign ‘ROOT’ to it. The pointer ‘TEMPROOT’ will act as a temporary ‘ROOT’ and will be used to traverse the ‘TRIE’.
  • Declare an integer variable, ‘i’ and assign ‘str.length() - 1’.
  • Run a loop while ‘i’ is greater than or equal to zero.
    • Declare an integer variable, ‘INDEX’ and assign STREAM[i] - ‘a’, that stores the index of the character in the ‘TRIE’.
    • If TEMPROOT->CHILD[INDEX] == NULL, that shows that the current character is not present in the ‘TRIE’. So, return false.
    • Else, update ‘TEMPROOT’ by ‘TEMPROOT->CHILD[INDEX]’.
    • If TEMPROOT->ISEND == true, that shows that a complete word is found. So, return true.
    • Else, decrement ‘i’ by 1.
  • Return ‘TEMPROOT->ISEND’.

Description of ‘insert’ function

This function will take one parameter :

STR: A string variable to store the string from ‘DICTIONARY’.

void insert(str):

• Declare a pointer of ‘TRIE’, ‘TEMPROOT’ and assign ‘ROOT’ to it. The pointer ‘TEMPROOT’ will act as a temporary ‘ROOT’ and will be used to traverse the ‘TRIE’.
• Declare an integer variable, ‘i’ and initialize with ‘STR.length() - 1’ to traverse the string, ‘STR’.
• Run a loop while ‘i’ is greater than or equal to zero
  • Declare an integer variable, ‘INDEX’ and assign STR[i] - ‘a’, that stores the index of the current character of ‘STR’ in the ‘TRIE’.
    • If TEMPROOT->CHILD[index] == NULL, that shows that the current character of ‘STR’ is not present in the ‘TRIE’. So, create a new node and update ‘TEMPROOT->CHILD[i]’ by the address of the new node.
  • Update ‘TEMPROOT’ by ‘TEMPROOT->CHILD[i]’.
  • Decrement ‘i’ by 1.
• Update ‘ROOT->ISEND’ by true.