LeetCode|1032. 字符流

题目链接：1032. 字符流

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

思路

由于字符流匹配后缀，在建树时可以将words的每个单词翻转、倒序建树。
用一个字符串存储读取的字符流。每次查询，将读取的字符加到串的头部，只需要在Trie树中查找到某一个 完整的前缀即可。
题目中，由于单个word 的长度小于等于 200 ，而查询次数最多 \(3 \times 10^4\) 次，故对于字符串很长的情况时，应当 传引用，并且只需要考查字符串的前200位即可。

方法

字典树

字典树如其名，实际是维护着一个字符串的字典库，我们可以把一系列已知的字符串看作先验知识，字典树就是以位的方式去将这些字符串进行存储。
也就是说字典树会存储每一位出现过的字符，并以这个字符为起点，去存储其下一位的字符情况，其本质就是一个多叉树，每一个分叉就存储一个字符。我们从多叉树的根节点出发沿着任意一条路径到达叶子节点就能还原某个字符串。如下图所示，蓝色字即为还原存储的字符串。

字典树的作用是用来查找的，如果我们直接把字符信息存储到节点上，还需要枚举每一个子节点去看其存储的字符是否为目标字符。因此我们可以做一个调整，用一个哈希表（数组）来将字符信息和子节点进行结合，存储每个子节点要存储的字符以及子节点本身，其实可以理解为一个嵌套的多级哈希表，每一级哈希表存储出现过的字符和这个字符对应的下一级哈希表。如下图所示，蓝色字即为还原存储的字符串。

Python代码

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False

class StreamChecker:

    def __init__(self, words: List[str]):
        self.root = Trie()
        for w in words:
            # 倒序构造字典树
            self.add_word(self.root, w[::-1])
        self.queryword = ""

    def add_word(self, root, word):
        cur = root
        for w in word:
            if w not in cur.children:
                cur.children[w] = Trie()
            cur = cur.children[w]
        cur.end = True

    def query(self, letter: str) -> bool:
        # 查询的字母也倒序拼接
        self.queryword = letter + self.queryword
        cur = self.root
        for w in self.queryword:
            if w not in cur.children:
                return False
            cur = cur.children[w]
            # 当前字母是结尾就直接返回
            if cur.end:
                return True
        return False