Leetcode #1032: Stream of Characters
In this guide, we solve Leetcode #1032 Stream of Characters in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Design, Trie, Array, String, Data Stream
Intuition
Prefix queries are most efficient with a trie.
Each character transitions to the next node in the tree.
Approach
Insert words into the trie and traverse by characters for queries.
Track terminal markers to distinguish full words from prefixes.
Steps:
- Build the trie.
- Traverse for each query.
- Return matches or validations.
Example
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
Python Solution
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, w: str):
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, w: List[str]) -> bool:
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
if node.is_end:
return True
return False
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = Trie()
self.cs = []
self.limit = 201
for w in words:
self.trie.insert(w)
def query(self, letter: str) -> bool:
self.cs.append(letter)
return self.trie.search(self.cs[-self.limit :])
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)
Complexity
The time complexity is O(total characters). The space complexity is O(total characters).
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.