1032. 字符流

题目地址(1032. 字符流)

https://leetcode-cn.com/problems/stream-of-characters/

题目描述

按下述要求实现 StreamChecker 类：

StreamChecker(words)：构造函数，用给定的字词初始化数据结构。
query(letter)：如果存在某些 k >= 1，可以用查询的最后 k个字符（按从旧到新顺序，包括刚刚查询的字母）拼写出给定字词表中的某一字词时，返回 true。否则，返回 false。


示例：

StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
streamChecker.query('a');          // 返回 false
streamChecker.query('b');          // 返回 false
streamChecker.query('c');          // 返回 false
streamChecker.query('d');          // 返回 true，因为 'cd' 在字词表中
streamChecker.query('e');          // 返回 false
streamChecker.query('f');          // 返回 true，因为 'f' 在字词表中
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' 在字词表中。


提示：

1 <= words.length <= 2000
1 <= words[i].length <= 2000
字词只包含小写英文字母。
待查项只包含小写英文字母。
待查项最多 40000 个。

前置知识

前缀树

公司

字节

思路

很明显，我们需要将历史 query 的字符全部记录下来。

比如：

streamChecker.query("a"); // stream： a
streamChecker.query("b"); // stream：ab
streamChecker.query("c"); // stream：abc

之后我们用拼接的单词在 words 中查询即可，最简单的方式当然是每次 query 都去扫描一次，这种方式时间复杂度为 $O(m n q)$，其中 m 和 n 分别为 words 的长度和， words[i] 的平均长度，m 和 n 最大为 2000，q 是待查项，最大为 40000，毫无疑问会超时。

我们可以采用构建 Trie 的形式，即以空间环时间，其代码和常规的 Trie 类似，只需要将 search(word) 函数做一个简单修改即可，我们不需要检查整个 word 是否存在，而已 word 的前缀存在即可。

提示：可以通过对 words 去重，来用空间换区时间。

具体算法：

init 中构建 Trie 和双端队列 stream
query 时，往 stream 的左边 append 即可。
调用 Trie 的 search（和常规的 search 稍有不同，我上面已经讲了）

以上面的例子为例：

streamChecker.query("a"); // stream： a
streamChecker.query("b"); // stream：ab
streamChecker.query("c"); // stream：abc

当 query("c") 的时候，我们需要查 abc，bc， c 三个是否有一个在 words 中。由于我们知道待查项的尾字符（在这个例子中尾字符是 c），因此从尾字符开始在前缀树中搜索，看是否能够搜索到 word 即可。这提示我们前缀树倒序插入或者 stream 倒序插入。

这里有两个小的点需要注意：

如果用数组来存储，由于每次都往数组头部插入一个元素，因此每次 query 操作的时间复杂度为 $O(N)$，其中 $N$ 为截止当前执行 query 的次数，我们可以使用双端队列进行优化。
由于不必 query 形成的查询全部命中。比如 stream 为 cba 的时候，找到单词 c， bc， abc 都是可以的。如果是找到 c，cb，cba 比较好吧，现在是反的。其实我们可以反序插入是，类似的技巧在211.add-and-search-word-data-structure-design 也有用到。

核心代码（Python）：

class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        self.stream = deque([])

        for word in set(words):
            self.trie.insert(word[::-1])

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        return self.trie.search(self.stream)

关键点解析

前缀树模板
倒序插入

代码

语言支持: Python

Python Code:

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.Trie = {}

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        curr = self.Trie
        for w in word:
            if w not in curr:
                curr[w] = {}
            curr = curr[w]
        curr['#'] = 1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        curr = self.Trie
        for w in word:
            if w not in curr:
                return False
            if "#" in curr[w]:
                return True
            curr = curr[w]
        return False


class StreamChecker:

    def __init__(self, words: List[str]):
        self.trie = Trie()
        self.stream = deque([])

        for word in set(words):
            self.trie.insert(word[::-1])

    def query(self, letter: str) -> bool:
        self.stream.appendleft(letter)
        return self.trie.search(self.stream)

题目地址(1032. 字符流)

题目描述

前置知识

公司

思路

关键点解析

代码

相关题目