字符流【LC1032】
设计一个算法：接收一个字符流，并检查这些字符的后缀是否是字符串数组
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。
- 思路：【字典树】
还是字典树的老套路，题目要求是与字符流的后缀匹配，因此将words逆序加入到字典树中，然后使用StringBuilder存储字符流中的字符，每加入一个字符判断是否有其后缀字符串在字典树中存在，同样以逆序的形式判断，如果某个节点的cnt大于0，那么表示有匹配的后缀 - 实现
class StreamChecker { StringBuilder sb; class TireNode{ TireNode[] next = new TireNode[26]; int cnt; } TireNode root; public void insert(String s){ TireNode p = root; for (int i = s.length() - 1; i >= 0; i--){ int u = s.charAt(i) - 'a'; if (p.next[u] == null) p.next[u] = new TireNode(); p = p.next[u]; } p.cnt++; } public StreamChecker(String[] words) { root = new TireNode(); sb = new StringBuilder(); for (String word : words){ insert(word); } } public boolean query(char letter) { sb.append(letter); TireNode p = root; for (int i = sb.length() - 1; i >= 0; i--){ int u = sb.charAt(i) - 'a'; if (p.next[u] == null) return false; p = p.next[u]; if (p.cnt > 0) return true; } return p.cnt > 0; } } /** * Your StreamChecker object will be instantiated and called as such: * StreamChecker obj = new StreamChecker(words); * boolean param_1 = obj.query(letter); */
