第六章 - 高频考题(困难)
1032. 字符流

题目地址(1032. 字符流)

题目描述

1
按下述要求实现 StreamChecker 类:
2
3
StreamChecker(words):构造函数,用给定的字词初始化数据结构。
4
query(letter):如果存在某些 k >= 1,可以用查询的最后 k个字符(按从旧到新顺序,包括刚刚查询的字母)拼写出给定字词表中的某一字词时,返回 true。否则,返回 false。
5
6
7
示例:
8
9
StreamChecker streamChecker = new StreamChecker(["cd","f","kl"]); // 初始化字典
10
streamChecker.query('a'); // 返回 false
11
streamChecker.query('b'); // 返回 false
12
streamChecker.query('c'); // 返回 false
13
streamChecker.query('d'); // 返回 true,因为 'cd' 在字词表中
14
streamChecker.query('e'); // 返回 false
15
streamChecker.query('f'); // 返回 true,因为 'f' 在字词表中
16
streamChecker.query('g'); // 返回 false
17
streamChecker.query('h'); // 返回 false
18
streamChecker.query('i'); // 返回 false
19
streamChecker.query('j'); // 返回 false
20
streamChecker.query('k'); // 返回 false
21
streamChecker.query('l'); // 返回 true,因为 'kl' 在字词表中。
22
23
24
提示:
25
26
1 <= words.length <= 2000
27
1 <= words[i].length <= 2000
28
字词只包含小写英文字母。
29
待查项只包含小写英文字母。
30
待查项最多 40000 个。
Copied!

前置知识

公司

  • 字节

思路

很明显,我们需要将历史 query 的字符全部记录下来。
比如:
1
streamChecker.query("a"); // stream: a
2
streamChecker.query("b"); // stream:ab
3
streamChecker.query("c"); // stream:abc
Copied!
之后我们用拼接的单词在 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 稍有不同, 我上面已经讲了)
以上面的例子为例:
1
streamChecker.query("a"); // stream: a
2
streamChecker.query("b"); // stream:ab
3
streamChecker.query("c"); // stream:abc
Copied!
当 query("c") 的时候,我们需要查 abc,bc, c 三个是否有一个在 words 中。由于我们知道待查项的尾字符(在这个例子中尾字符是 c),因此从尾字符开始在前缀树中搜索,看是否能够搜索到 word 即可。这提示我们前缀树倒序插入或者 stream 倒序插入
这里有两个小的点需要注意:
  1. 1.
    如果用数组来存储, 由于每次都往数组头部插入一个元素,因此每次 query 操作的时间复杂度为 $O(N)$,其中 $N$ 为截止当前执行 query 的次数,我们可以使用双端队列进行优化。
  2. 2.
    由于不必 query 形成的查询全部命中。比如 stream 为 cba 的时候,找到单词 c, bc, abc 都是可以的。如果是找到 c,cb,cba 比较好吧,现在是反的。其实我们可以反序插入是,类似的技巧在211.add-and-search-word-data-structure-design 也有用到。
核心代码(Python):
1
class StreamChecker:
2
3
def __init__(self, words: List[str]):
4
self.trie = Trie()
5
self.stream = deque([])
6
7
for word in set(words):
8
self.trie.insert(word[::-1])
9
10
def query(self, letter: str) -> bool:
11
self.stream.appendleft(letter)
12
return self.trie.search(self.stream)
Copied!

关键点解析

  • 前缀树模板
  • 倒序插入

代码

  • 语言支持: Python
Python Code:
1
class Trie:
2
3
def __init__(self):
4
"""
5
Initialize your data structure here.
6
"""
7
self.Trie = {}
8
9
def insert(self, word):
10
"""
11
Inserts a word into the trie.
12
:type word: str
13
:rtype: void
14
"""
15
curr = self.Trie
16
for w in word:
17
if w not in curr:
18
curr[w] = {}
19
curr = curr[w]
20
curr['#'] = 1
21
22
def search(self, word):
23
"""
24
Returns if the word is in the trie.
25
:type word: str
26
:rtype: bool
27
"""
28
curr = self.Trie
29
for w in word:
30
if w not in curr:
31
return False
32
if "#" in curr[w]:
33
return True
34
curr = curr[w]
35
return False
36
37
38
class StreamChecker:
39
40
def __init__(self, words: List[str]):
41
self.trie = Trie()
42
self.stream = deque([])
43
44
for word in set(words):
45
self.trie.insert(word[::-1])
46
47
def query(self, letter: str) -> bool:
48
self.stream.appendleft(letter)
49
return self.trie.search(self.stream)
Copied!

相关题目