1032. 字符流 · ttttt

# 1032. 字符流 ## 题目地址(1032. 字符流) <https://leetcode-cn.com/problems/stream-of-characters/> ## 题目描述 ``` <pre class="calibre18">``` 按下述要求实现 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 存起来形成一个单词 stream。比如： ``` <pre class="calibre18">``` streamChecker.query("a"); // stream： a streamChecker.query("b"); // stream：ba streamChecker.query("c"); // stream：cba ``` ``` 这里有两个小的点需要注意： 1. 如果用数组来存储，由于每次都往数组头部插入一个元素，因此每次 query 操作的时间复杂度为 O(N)O(N)O(N)，其中 NNN 为截止当前执行 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) 也有用到。之后我们用拼接的单词在 words 中查询即可，最简单的方式当然是每次 query 都去扫描一次，这种方式毫无疑问会超时。我们可以采用构建 Trie 的形式，即已空间环时间，其代码和常规的 Trie 类似，只需要将 search(word) 函数做一个简单修改即可，我们不需要检查整个 word 是否存在，而已 word 的前缀存在即可。 > 提示：可以通过对 words 去重，来用空间换区时间。具体算法： - init 中构建 Trie 和双端队列 stream - query 时，往 stream 的左边 append 即可。 - 调用 Trie 的 search（和常规的 search 稍有不同，我上面已经讲了）核心代码（Python）： ``` <pre class="calibre18">``` 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: ``` <pre class="calibre18">``` 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)