LC.P1032[字符流]困难

题目描述

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

方法一：Trie

在构造函数中，遍历字符串数组words，对于每个字符串word，将其反转后逐个插入到前缀树中，插入结束后，将isEnd设为true。

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
class StreamChecker {

    Trie trie;
    StringBuilder builder;

    public StreamChecker(String[] words) {
        trie = new Trie();
        for (String word : words) trie.insert(word);
        builder = new StringBuilder();
    }

    public boolean query(char letter) {
        builder.append(letter);
        return trie.query(builder);
    }

    private static class Trie {
        private Trie[] next;
        private boolean isEnd;

        public Trie() {
            next = new Trie[26];
            isEnd = false;
        }

        public void insert(String word) {
            Trie node = this;
            for (int i = word.length() - 1; i >= 0; --i) {
                char c = word.charAt(i);
                if (node.next[c - 'a'] == null) {
                    node.next[c - 'a'] = new Trie();
                }
                node = node.next[c - 'a'];
            }
            node.isEnd = true;
        }

        public boolean query(StringBuilder word) {
            Trie node = this;
            for (int i = word.length() - 1; i >= 0; --i) {
                char c = word.charAt(i);
                if (node.next[c - 'a'] == null) return false;
                node = node.next[c - 'a'];
                if (node.isEnd) return true;
            }
            return false;
        }
    }
}

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker obj = new StreamChecker(words);
 * boolean param_1 = obj.query(letter);
 */