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$ 构建前缀树,前缀树的每个节点包含两个属性:
children
:指向 $26$ 个字母的指针数组,用于存储当前节点的子节点。is_end
:标记当前节点是否为某个字符串的结尾。
在构造函数中,我们遍历字符串数组 $words$,对于每个字符串 $w$,我们将其反转后,逐个字符插入到前缀树中,插入结束后,将当前节点的 is_end
标记为 true
。
在 query
函数中,我们将当前字符 $c$ 加入到字符流中,然后从后往前遍历字符流,对于每个字符 $c$,我们在前缀树中查找是否存在以 $c$ 为结尾的字符串,如果存在,返回 true
,否则返回 false
。注意到 $words$ 中的字符串长度不超过 $200$,因此查询时最多只需要遍历 $200$ 个字符。
时间复杂度方面,构造函数的时间复杂度为 $O(L)$,而 query
函数的时间复杂度为 $O(M)$。其中 $L$ 为字符串数组 $words$ 中所有字符串的长度之和,而 $M$ 为字符串数组 $words$ 中字符串的最大长度。空间复杂度 $O(L)$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
|