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.

#1032

Hard

auto_awesome数组·string

LeetCode 题解工作台

字符流

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。例如， words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a' 、 'x' 、 'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与…

数组字符串设计字典树数据流

题目描述

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。

例如，words = ["abc", "xyz"] 且字符流中逐个依次加入 4 个字符 'a'、'x'、'y' 和 'z' ，你所设计的算法应当可以检测到 "axyz" 的后缀 "xyz" 与 words 中的字符串 "xyz" 匹配。

按下述要求实现 StreamChecker 类：

StreamChecker(String[] words) ：构造函数，用字符串数组 words 初始化数据结构。
boolean query(char letter)：从字符流中接收一个新字符，如果字符流中的任一非空后缀能匹配 words 中的某一字符串，返回 true ；否则，返回 false。

示例：

输入：
["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"]]
输出：
[null, false, false, false, true, false, true, false, false, false, false, false, true]

解释：
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // 返回 False
streamChecker.query("b"); // 返回 False
streamChecker.query("c"); // 返回n False
streamChecker.query("d"); // 返回 True ，因为 'cd' 在 words 中
streamChecker.query("e"); // 返回 False
streamChecker.query("f"); // 返回 True ，因为 'f' 在 words 中
streamChecker.query("g"); // 返回 False
streamChecker.query("h"); // 返回 False
streamChecker.query("i"); // 返回 False
streamChecker.query("j"); // 返回 False
streamChecker.query("k"); // 返回 False
streamChecker.query("l"); // 返回 True ，因为 'kl' 在 words 中

提示：

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] 由小写英文字母组成
letter 是一个小写英文字母
最多调用查询 4 * 10⁴ 次

lightbulb

解题思路

方法一：前缀树

我们可以根据初始化时的字符串数组 $words$ 构建前缀树，前缀树的每个节点包含两个属性：

children：指向 $26$ 个字母的指针数组，用于存储当前节点的子节点。
is_end：标记当前节点是否为某个字符串的结尾。

在构造函数中，我们遍历字符串数组 $words$ ，对于每个字符串 $w$ ，我们将其反转后，逐个字符插入到前缀树中，插入结束后，将当前节点的 is_end 标记为 true。

在 query 函数中，我们将当前字符 $c$ 加入到字符流中，然后从后往前遍历字符流，对于每个字符 $c$ ，我们在前缀树中查找是否存在以 $c$ 为结尾的字符串，如果存在，返回 true，否则返回 false。注意到 $words$ 中的字符串长度不超过 $200$ ，因此查询时最多只需要遍历 $200$ 个字符。

时间复杂度方面，构造函数的时间复杂度为 $O(L)$ ，而 query 函数的时间复杂度为 $O(M)$ 。其中 $L$ 为字符串数组 $words$ 中所有字符串的长度之和，而 $M$ 为字符串数组 $words$ 中字符串的最大长度。空间复杂度 $O(L)$ 。

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

43

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)

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#745 前缀和后缀搜索 #1023 驼峰式匹配 #1178 猜字谜