#1032

Hard

LeetCode Problem Workspace

Stream of Characters

Implement a StreamChecker that detects if any suffix of a character stream matches a given list of words using efficient design.

array string design trie data stream

Problem Statement

Design a class StreamChecker that takes an array of strings words during initialization. The class should process a continuous stream of lowercase letters, and for each new character, determine if any suffix of the characters seen so far forms one of the words in words.

For example, given words = ["abc", "xyz"] and a stream that sequentially receives 'a', 'x', 'y', 'z', the StreamChecker should identify that the suffix "xyz" of the stream "axyz" matches the word "xyz". Implement the StreamChecker class with a query method that returns true if the current stream suffix matches any word, false otherwise.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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 <= 2000
1 <= words[i].length <= 200
words[i] consists of lowercase English letters.
letter is a lowercase English letter.
At most 4 * 104 calls will be made to query.

Solution Approach

Reverse Trie Construction

Insert all words into a trie in reversed order, so that suffix matching becomes prefix traversal in the trie. This transforms the problem into checking prefixes in a reversed stream efficiently.

Stream Pointer Management

Maintain active pointers in the trie for each incoming character. Move existing pointers along trie edges corresponding to the new character and start a new pointer from the root. If any pointer reaches a word end, return true.

Optimized Query Handling

Limit pointer traversal to the maximum word length to prevent unnecessary checks. Store the stream in a fixed-size buffer to efficiently track only recent characters relevant for suffix matching.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(L) per query where L is the maximum word length, since each query only traverses at most L trie nodes. Space complexity is O(S) for storing the reversed trie and O(L) for the buffer of recent characters, where S is the total number of characters across all words.

What Interviewers Usually Probe

Pay attention to trie design and reversed insertion for suffix queries.
Ensure query performance scales with stream length, not total characters seen.
Be ready to discuss pointer management and memory optimization for active streams.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse words in the trie, causing inefficient suffix checks.
Scanning the entire stream each query instead of limiting to maximum word length.
Not handling overlapping matches, leading to incorrect true/false responses.

Follow-up variants

Check for multiple streams simultaneously, requiring separate pointer sets per stream.
Allow wildcard characters in words, introducing more complex trie traversal logic.
Return all matching words per query instead of just a boolean result.

FAQ

What is the core idea behind the Stream of Characters problem?

Use a reversed trie to track word suffixes efficiently, converting suffix detection into prefix traversal of incoming characters.

How do I efficiently manage the character stream?

Maintain a fixed-size buffer of recent characters equal to the maximum word length to limit unnecessary checks.

Why reverse the words in the trie?

Reversing allows checking suffixes as prefixes, enabling O(1) traversal per new character with active pointers.

Can overlapping matches affect the results?

Yes, multiple active pointers handle overlapping matches to ensure correct detection of all valid suffixes.

What is the pattern emphasized in this problem?

This problem exemplifies the Array plus String pattern where streams must be matched against a set of predefined words efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

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)

Continue Practicing

#745 prefix and suffix search #1023 camelcase matching #1178 number of valid words for each puzzle