[LeetCode] 1032. Stream of Characters-526互联

Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.

For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.

Implement the StreamChecker class:

StreamChecker(String[] words) Initializes the object with the strings array words.
boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.

Example 1:

Input
["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"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]

Explanation
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist

Constraints:

1 <= words.length <= 2000
1 <= words[i].length <= 200
words[i] consists of lowercase English letters.
letter is a lowercase English letter.
At most 4 * 104 calls will be made to query.

字符流。

设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 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。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/stream-of-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目读完之后，不难想到思路是字典树。这道题跟一般字典树有所不同的地方是他找的是后缀，我们可以把每一个需要插入字典的单词逆序插进去，这样我们检查的时候，还是按照前缀的方式检查。其余部分跟一般的字典树题目一样，建议先做 208 和 211 题。

时间

insert() - O(mn) - 单词平均长度 m * n 个单词

query() - O(1)

空间O(n)

Java实现

 1 class Node {
 2     Node[] children = new Node[26];
 3     boolean isEnd = false;
 4 
 5     public void insert(String s) {
 6         Node node = this;
 7         for (int i = s.length() - 1; i >= 0 ; i--) {
 8             int j = s.charAt(i) - 'a';
 9             if (node.children[j] == null) {
10                 node.children[j] = new Node();
11             }
12             node = node.children[j];
13         }
14         node.isEnd = true;
15     }
16 
17     public boolean query(StringBuilder sb) {
18         Node node = this;
19         for (int i = sb.length() - 1, j = 0; i >= 0 && j < 201; i--, j++) {
20             int index = sb.charAt(i) - 'a';
21             if (node.children[index] == null) {
22                 return false;
23             }
24             node = node.children[index];
25             if (node.isEnd) {
26                 return true;
27             }
28         }
29         return false;
30     }
31 }
32 
33 class StreamChecker {
34     private StringBuilder sb = new StringBuilder();
35     private Node node = new Node();
36 
37     public StreamChecker(String[] words) {
38         for (String w : words) {
39             node.insert(w);
40         }
41     }
42     
43     public boolean query(char letter) {
44         sb.append(letter);
45         return node.query(sb);
46     }
47 }
48 
49 /**
50  * Your StreamChecker object will be instantiated and called as such:
51  * StreamChecker obj = new StreamChecker(words);
52  * boolean param_1 = obj.query(letter);
53  */