Stream of Characters

• In the StreamChecker constructor, convert the words array into a HashSet for fast lookups. Also, find the maximum length (maxWordLength) of any word in the list.
• Maintain a StringBuilder, streamHistory, to keep track of the characters received.
• For each query(letter) call:
  1. Append the new letter to streamHistory.
  2. Iterate backwards from the end of streamHistory.
  3. In each iteration, extract a suffix.
  4. Limit the check to suffixes with length up to maxWordLength.
  5. For each extracted suffix, check if it exists in the wordSet.
  6. If a match is found, return true immediately.
  7. If the loop completes without finding any matching suffix, return false.

In the StreamChecker constructor, we convert the input words array into a HashSet for efficient O(1) average time lookups. We also pre-calculate the maximum length of any word in the dictionary to avoid checking unnecessarily long suffixes. A StringBuilder is used to store the characters from the stream.

In the query(char letter) method, we first append the new letter to our StringBuilder. Then, we iterate backwards from the end of the stream, forming a new suffix in each step. For each suffix, we check for its existence in the HashSet of words. If a match is found, we immediately return true. If we check all possible suffixes (with length up to maxWordLength) and find no match, we return false.

1import java.util.Arrays;2import java.util.HashSet;3import java.util.Set;4 5class StreamChecker {6    private Set<String> wordSet;7    private StringBuilder streamHistory;8    private int maxWordLength;9 10    public StreamChecker(String[] words) {11        wordSet = new HashSet<>(Arrays.asList(words));12        streamHistory = new StringBuilder();13        maxWordLength = 0;14        for (String word : words) {15            maxWordLength = Math.max(maxWordLength, word.length());16        }17    }18 19    public boolean query(char letter) {20        streamHistory.append(letter);21        // We only need to check suffixes up to maxWordLength22        for (int i = streamHistory.length() - 1; i >= 0 && streamHistory.length() - i <= maxWordLength; i--) {23            String suffix = streamHistory.substring(i);24            if (wordSet.contains(suffix)) {25                return true;26            }27        }28        return false;29    }30}

• Define a TrieNode class with a children array (for each letter) and an isWord boolean flag.
• In the StreamChecker constructor:
  1. Initialize a TrieNode root.
  2. For each word in the input words array, insert its reversed version into the Trie. Mark the node corresponding to the end of the reversed word by setting isWord = true.
  3. Initialize a StringBuilder streamHistory to store the stream.
• For each query(letter) call:
  1. Append the letter to streamHistory.
  2. Start a traversal from the root of the Trie.
  3. Iterate backwards through streamHistory, starting from the last character.
  4. For each character, move down the Trie. If a path does not exist (null child), it means no word can be formed, so break and return false.
  5. If at any point the traversal reaches a node where isWord is true, a valid suffix has been found, so return true.
  6. If the backward traversal completes without finding a word, return false.

First, we design a TrieNode class. In the StreamChecker constructor, we build a Trie by inserting every word from the input array in reverse order. For example, if words contains "abc", we insert "cba" into the Trie. We mark the node corresponding to the last character of the inserted reversed word (i.e., the node for 'a') to indicate that it forms a complete word.

For each query(char letter), we append the new character to our stream history (e.g., a StringBuilder). Then, we traverse this history backwards, starting from the newest character, and simultaneously traverse our Trie from the root. If we can trace a path in the Trie that corresponds to a reversed word, it means the current suffix of our stream matches a word in the dictionary. For instance, if the stream is "...xya" and we have "abc" in our dictionary (stored as "cba" in the Trie), when we query 'b' and then 'c', the backward traversal c -> b -> a will find a match in the Trie.

The backward traversal is naturally bounded by the maximum depth of the Trie, which is the length of the longest word, making each query very fast.

1class StreamChecker {2    class TrieNode {3        TrieNode[] children = new TrieNode[26];4        boolean isWord = false;5    }6 7    private final TrieNode root;8    private final StringBuilder streamHistory;9 10    public StreamChecker(String[] words) {11        root = new TrieNode();12        streamHistory = new StringBuilder();13        14        for (String word : words) {15            TrieNode curr = root;16            // Insert word in reverse order17            for (int i = word.length() - 1; i >= 0; i--) {18                int index = word.charAt(i) - 'a';19                if (curr.children[index] == null) {20                    curr.children[index] = new TrieNode();21                }22                curr = curr.children[index];23            }24            curr.isWord = true;25        }26    }27 28    public boolean query(char letter) {29        streamHistory.append(letter);30        TrieNode curr = root;31        // Traverse backwards from the end of the stream.32        // The loop is implicitly bounded by the max depth of the Trie (max word length),33        // because if a path doesn't exist, curr becomes null and the loop terminates.34        for (int i = streamHistory.length() - 1; i >= 0; i--) {35            int index = streamHistory.charAt(i) - 'a';36            if (curr.children[index] == null) {37                return false;38            }39            curr = curr.children[index];40            if (curr.isWord) {41                return true;42            }43        }44        return false;45    }46}