Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.
For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.
Implement the StreamChecker class:
StreamChecker(String[] words) Initializes the object with the strings array words.boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.Example 1:
Input
["StreamChecker", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query", "query"]
[[["cd", "f", "kl"]], ["a"], ["b"], ["c"], ["d"], ["e"], ["f"], ["g"], ["h"], ["i"], ["j"], ["k"], ["l"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]
Explanation
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 200words[i] consists of lowercase English letters.letter is a lowercase English letter.4 * 104 calls will be made to query.The key challenge in #1032 Stream of Characters is efficiently checking whether the current stream of queried characters forms a suffix that matches any word from a given dictionary. Since queries arrive one character at a time, repeatedly scanning all words would be too slow.
A common strategy is to use a Trie (prefix tree), but with a twist: store each word in reversed order. As characters arrive from the stream, maintain a running buffer of recent characters and traverse the Trie from the newest character backward. This effectively converts the suffix-matching problem into a prefix search inside the Trie.
If during traversal you reach a node marked as the end of a word, a match exists. This approach significantly reduces repeated comparisons and allows quick incremental checks for each query.
With a well-structured Trie and bounded stream length, each query can be processed efficiently while keeping memory usage manageable.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Reversed Trie with Stream Buffer | O(L) per query, where L is the maximum word length | O(N * L) for storing words in the Trie |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Put the words into a trie, and manage a set of pointers within that trie.
This approach utilizes a reversed Trie (prefix tree) to efficiently manage and query suffixes of input characters. By storing the reversed words in a Trie, we can match suffixes of the input stream by querying from the current character backwards. For each character queried, we move through the Trie from those characters up to a certain limit (or until no further match) to see if any of the suffixes match one of the stored words.
Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class StreamChecker:
7 def __init__(self, words):
8 self.root = TrieNode()
9 self.stream = []
10 for word in words:
11 node = self.root
12 for char in reversed(word):
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.is_end_of_word = True
17
18 def query(self, letter):
19 self.stream.append(letter)
20 node = self.root
21 for char in reversed(self.stream):
22 if node.is_end_of_word:
23 return True
24 if char not in node.children:
25 return False
26 node = node.children[char]
27 return node.is_end_of_wordThe implementation involves creating a Trie that stores each word in reverse. When a query is made, characters are added to a list representing the current stream. We then check from the current end of the stream backwards through the Trie to determine if any suffix matches a word.
The Aho-Corasick algorithm is useful for searching multiple 'dictionary' words within a text. We build an automaton with all words and query the stream letters. This data structure enables matching of all dictionary words in parallel through a finite state machine that jumps quickly between states even upon mismatches.
Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.
1class TrieNode {
2 constructor(
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Stream of Characters are commonly discussed in FAANG-style interviews because they test knowledge of Tries, streaming data handling, and efficient query design. It also evaluates a candidate's ability to optimize repeated lookups.
The optimal approach uses a Trie where words are inserted in reversed order. As characters stream in, you traverse the Trie using the recent characters in reverse to check if any suffix matches a word. This allows efficient query processing without rechecking every dictionary word.
Words are reversed so that suffix matching becomes equivalent to prefix traversal in the Trie. When a new character arrives, you traverse from the latest character backward and follow Trie edges until a match or failure occurs.
A Trie (prefix tree) is the most suitable data structure for this problem. By reversing the words before inserting them, the Trie enables fast suffix matching as characters arrive in the stream.
The JavaScript version also uses the Aho-Corasick automaton. We have created trie nodes, inserted the words in reverse, and then built failure links between nodes to allow for fast lookup during the query.