# 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 个。
```

## 前置知识

* [前缀树](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/trie)

## 公司

* 字节

## 思路

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

比如：

```javascript
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 稍有不同， 我上面已经讲了）

以上面的例子为例：

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

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

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

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

核心代码（Python）：

```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:

```python
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)
```

## 相关题目

* [0208.implement-trie-prefix-tree](https://github.com/azl397985856/leetcode/blob/b8e8fa5f0554926efa9039495b25ed7fc158372a/problems/208.implement-trie-prefix-tree.md)
* [0211.add-and-search-word-data-structure-design](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/211.add-and-search-word-data-structure-design.md)
* [0212.word-search-ii](https://github.com/azl397985856/leetcode/blob/b0b69f8f11dace3a9040b54532105d42e88e6599/problems/212.word-search-ii.md)
* [0472.concatenated-words](https://github.com/azl397985856/leetcode/blob/master/problems/472.concatenated-words.md)
* [0820.short-encoding-of-words](https://github.com/azl397985856/leetcode/blob/master/problems/820.short-encoding-of-words.md)