【数据结构运用】常规 Trie 运用及其优化
题目描述
这是 LeetCode 上的「1032. 字符流」，难度为「困难」。
Tag : 「字典树」、「枚举」、「剪枝」
设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。
例如，words = ["abc", "xyz"] 且字符流中逐个依次加入
个字符 '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 中
提示：
words[i]由小写英文字母组成letter是一个小写英文字母- 最多调用查询
次
Trie + 枚举
先考虑最为简单的做法：将给定的所有
顺序插入字典树，根据数据范围可知这一步计算量为
，其中最大的
长度只有
。
然后利用
长度只有
这一条件，直接使用「枚举」的方式来实现 query。
具体的，我们可以先使用一个字符串 s 来记录 query 操作产生的数据流，然后实现一个 boolean query(int start, int end) 方法，该方法会检查字典树中是否存在
子串。
由于
长度只有
（假设当前 s 的长度为
），因此我们只需要枚举「
作为子串左端点，
作为子串右端点」是否存在字典树中（是否存在
中）即可，最坏情况下，单次 query 操作计算量为
。
❝一些细节：为了避免每个样例都
new大数组，我们可以使用static优化。同时不了解 Trie 的同学可以先看前置🧀 : 实现 Trie 的两种方式。 ❞
代码：
class StreamChecker {
static int N = 2010 * 200, idx = 0;
static int[][] tr = new int[N][26];
static boolean[] isEnd = new boolean[N * 26];
StringBuilder sb = new StringBuilder();
void add(String s) {
int p = 0;
for (int i = 0; i < s.length(); i++) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
isEnd[p] = true;
}
boolean query(int start, int end) {
int p = 0;
for (int i = start; i <= end; i++) {
int u = sb.charAt(i) - 'a';
if (tr[p][u] == 0) return false;
p = tr[p][u];
}
return isEnd[p];
}
public StreamChecker(String[] words) {
for (int i = 0; i <= idx; i++) {
Arrays.fill(tr[i], 0);
isEnd[i] = false;
}
idx = 0;
for (String s : words) add(s);
}
public boolean query(char c) {
sb.append(c);
int n = sb.length(), min = Math.max(0, n - 200);
for (int i = n - 1; i >= min; i--) {
if (query(i, n - 1)) return true;
}
return false;
}
}
- 时间复杂度：
StreamChecker初始化复杂度为
，其中
为 words 字符总数；query 操作复杂度为
，其中
为最大 words[i] 长度
- 空间复杂度：
，其中
为 words 字符总数，
为字符集大小
Trie（优化）
初始化将所有的
存入 Trie 是必然的，我们只能考虑如何优化 query 操作。
在解法一中，我们需要对新数据流对应的字符串的每个后缀进行搜索，同时每次搜索是相互独立的，即本次匹配不会对下一次匹配产生贡献。
「实际上，我们可以通过「倒序建 Trie」的方式，将「枚举检查多个后缀」的操作变为「匹配一次后缀」操作。」
具体的，我们可以在初始化 StreamChecker 时，将每个
翻转（倒序）加入 Trie 中；然后在 query 操作时（假设当前数据流对应的字符串为 s，长度为
），从 s 的尾部开始在 Trie 中进行检索（即从
开始往回找）。
若在某个位置 idx 时匹配成功，意味着
的翻转子串在字典树中，同时我们又是将每个 words[i] 进行倒序插入，即意味着
的正向子串在 words 中，即满足 s 的某个后缀出现在 words 中。
同理，我们可以利用最大的 words[i] 长度为
来控制从
开始往回找的最远距离，同时利用当某个短后缀不在 Trie 中，则其余长度更大的后缀必然不在 Trie 中进行剪枝操作。
代码：
class StreamChecker {
static int N = 2010 * 200, idx = 0;
static int[][] tr = new int[N][26];
static boolean[] isEnd = new boolean[N * 26];
StringBuilder sb = new StringBuilder();
void add(String s) {
int p = 0;
for (int i = s.length() - 1; i >= 0; i--) {
int u = s.charAt(i) - 'a';
if (tr[p][u] == 0) tr[p][u] = ++idx;
p = tr[p][u];
}
isEnd[p] = true;
}
public StreamChecker(String[] words) {
for (int i = 0; i <= idx; i++) {
Arrays.fill(tr[i], 0);
isEnd[i] = false;
}
idx = 0;
for (String s : words) add(s);
}
public boolean query(char c) {
sb.append(c);
int n = sb.length(), min = Math.max(0, n - 200), p = 0;
for (int i = n - 1; i >= min; i--) {
if (isEnd[p]) return true;
int u = sb.charAt(i) - 'a';
if (tr[p][u] == 0) return false;
p = tr[p][u];
}
return isEnd[p];
}
}
- 时间复杂度：
StreamChecker初始化复杂度为
，其中
为 words 字符总数；query 操作复杂度为
，其中
为最大 words[i] 长度
- 空间复杂度：
，其中
为 words 字符总数，
为字符集大小
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1032 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
腾讯云开发者
