字符流

难度: Hard

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 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⁴ 次

Submission

运行时间: 298 ms

内存: 46.4 MB

from collections import defaultdict
from typing import List

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.is_word = False

class StreamChecker:
    def __init__(self, words: List[str]):
        self.root = TrieNode()
        self.stream = []

        # 将 words 中的每个单词反转并插入到字典树中
        for word in words:
            node = self.root
            for ch in reversed(word):
                node = node.children[ch]
            node.is_word = True

    def query(self, letter: str) -> bool:
        # 将新字符添加到字符流中
        self.stream.append(letter)

        # 在字典树中查询字符流的后缀
        node = self.root
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True

        return False


# 示例测试
words = ["cd", "f", "kl"]
obj = StreamChecker(words)
print(obj.query("a"))  # False
print(obj.query("b"))  # False
print(obj.query("c"))  # False
print(obj.query("d"))  # True
print(obj.query("e"))  # False
print(obj.query("f"))  # True
print(obj.query("g"))  # False
print(obj.query("h"))  # False
print(obj.query("i"))  # False
print(obj.query("j"))  # False
print(obj.query("k"))  # False
print(obj.query("l"))  # True

Explain

该题解采用字典树（Trie）数据结构，通过反转每个单词并将其插入到字典树中来处理字符流中的后缀匹配。每当接收到新的字符，它会被添加到一个字符流数组中，然后从最新的字符开始向前检查，使用字典树判断当前字符流的后缀是否为字典树中某个单词的前缀。如果在字典树中找到了对应的单词，那么返回true，否则继续检查。

时间复杂度: O(n*m) ，其中 n 是查询次数，m 是最长单词的长度

空间复杂度: O(T) ，其中 T 是所有单词的总字符数

from collections import defaultdict
from typing import List

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)  # 子节点用字典表示，键为字符，值为对应的 TrieNode
        self.is_word = False  # 标记该节点是否为某个单词的结束

class StreamChecker:
    def __init__(self, words: List[str]):
        self.root = TrieNode()  # 字典树的根节点
        self.stream = []  # 存储接收的字符流
        # 将每个单词反转并插入字典树
        for word in words:
            node = self.root
            for ch in reversed(word):
                node = node.children[ch]
            node.is_word = True  # 标记单词结束的节点

    def query(self, letter: str) -> bool:
        self.stream.append(letter)  # 将新字符添加到字符流中
        node = self.root
        # 从最新的字符开始反向在字典树中查找
        for ch in reversed(self.stream):
            if ch not in node.children:
                return False
            node = node.children[ch]
            if node.is_word:
                return True  # 如果找到了单词，返回 True
        return False  # 如果没有匹配的单词，返回 False

Explore

将每个单词反转后插入字典树是为了便于处理字符流中的后缀匹配。在字符流问题中，我们通常需要检查流的任何后缀是否能与字典中的单词匹配。如果单词未经反转直接插入字典树，我们需要从字典树的根节点开始，根据字符流的整个历史来匹配，这会变得复杂且低效，特别是当字符流非常长时。反转单词并存储在字典树中，使得我们可以仅通过查看流中的最后几个字符（即最新的字符）就能高效地进行匹配。这是因为反转后，字典树的路径与字符流的后缀直接对应。

在`query`方法中，从最新的字符开始反向查找是因为我们存储的单词是反转后的形式。当新字符加入到流中时，我们需要检查这个字符以及它之前的字符序列是否能够形成字典树中某个单词的前缀。由于字典树中存储的是反转的单词，所以我们需要从字符流的最新字符（即最后一个字符）开始，逆序检查这些字符是否能形成字典树中的路径。这样可以迅速定位到最新加入的字符可能形成的单词，提高匹配效率。

在字典树中的`is_word`属性标记了某个节点是否为单词的结束。当在字典树中插入单词时，单词的最后一个字符对应的节点会将`is_word`设置为`True`。这意味着，如果在查询字符流时，我们到达了一个标记为`is_word`的节点，这表明我们从最新的字符开始到当前节点形成的字符串序列，正好是字典树中存储的某个完整单词。因此，`is_word`属性确保我们不仅匹配到了单词的一部分，而是匹配到了一个完整的单词。

在`query`方法中，如果当前后缀匹配失败，即在字典树中找不到继续深入的路径，那么就不需要继续查找剩余的字符流了。这是因为，一旦某个字符没有在当前节点的孩子中找到对应的路径，这表明从这个字符开始的任何后续字符组合都不会形成有效的单词前缀。因此，函数会返回`False`，表示当前字符流的后缀与字典树中的任何单词都不匹配。此时，无需继续检查更早的字符，因为它们也不可能形成有效的匹配。