Stream of Characters

class TrieNode {
    Map<Character, TrieNode> map = new HashMap<>();
    boolean endOfWord = false;
}
    
class StreamChecker {
    TrieNode root = new TrieNode();
    Deque<Character> history = new LinkedList<>();
    
    public StreamChecker(String[] words) {
        for (String word : words) {
            TrieNode node = root;
            String reversed = new StringBuilder(word).reverse().toString();
            for (char character : reversed.toCharArray()) {
                if (!node.map.containsKey(character)) {
                    node.map.put(character, new TrieNode());
                }
                node = node.map.get(character);
            }
            node.endOfWord = true;
        }
    }
        
    public boolean query(char letter) {
        history.addFirst(letter);
            
        TrieNode node = root;
        for (char character : history) {
            if (node.endOfWord) {
                return true;
            }
            if (!node.map.containsKey(character)) {
                return false;
            }
            node = node.map.get(character);
        }
        return node.endOfWord;
    }
}

The goal of the provided Java solution is to determine if any substring of the received characters matches with any word out of the provided list using a Trie and a stream processing approach.

• A TrieNode class is defined where:

  • map holds the children nodes.
  • endOfWord indicates the end of a word.

• The StreamChecker class is responsible for:

  1. Initializing the Trie based on the reversed words to simplify suffix checking. This is done in the StreamChecker constructor where each input word is reversed and inserted into the Trie.
  2. Checking the incoming characters against the Trie dynamically. This operation is performed in the query method by adding the new character to the front of a history deque which represents the stream of characters received so far.

• The query method processes each incoming letter by:

  1. Adding each character to a history.
  2. Iteratively checking each character from the deque against the Trie.
  3. Returning true if a substring of the characters corresponds to a word end in the Trie.

This setup allows efficient checking of substrings against a predefined set of words by leveraging the Trie’s compact structure and quick lookup capabilities. The use of history to keep recent characters and the Trie construction for reversed words are critical for ensuring that the stream processing is both effective and efficient.

class WordStreamChecker:
    
    def __init__(self, words: List[str]):
        self.root = {}
        self.incomingChars = deque([])
    
        for word in set(words):
            currentNode = self.root     
            for character in reversed(word):
                if character not in currentNode:
                    currentNode[character] = {}
                currentNode = currentNode[character]
            currentNode['`'] = word
            
    def checkQuery(self, character: str) -> bool:
        self.incomingChars.appendleft(character)
            
        currentNode = self.root
        for char in self.incomingChars:
            if '`' in currentNode:
                return True
            if char not in currentNode:
                return False
            currentNode = currentNode[char]
        return '$' in currentNode

The given Python script defines a class WordStreamChecker to manage a stream of characters and check for the presence of specific words within this stream. Here's a concise explanation of how the implementation accomplishes this:

• Class Initialization (__init__ method):

  • Initializes a trie data structure to efficiently store and access words.
  • The words argument, a list of strings, is converted into a unique set to avoid duplicates and then stored in a trie in reverse order. This reverse storage is crucial as the stream of characters will be evaluated from most recent to older entries.
  • A special marker '`' is added at the end node of each word in the trie to signify the completion of a word.

• Character Stream Handling (checkQuery method):

  • Receives a character and adds it to a deque which maintains the current stream of characters.
  • It then checks, starting from the most recent character added, whether a sequence of these characters exists in the trie and forms a word that was originally input.

This setup allows the caller to continuously feed characters into the checkQuery method and receive immediate feedback on whether the recent sequence of characters has formed a complete word that exists in the initial list. It effectively handles multiple checks efficiently by leveraging the trie's properties and the deque's fast appends and pops.