【每日一题Day156】LC1032字符流 | 字典树

字符流【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);*/
  

  • 复杂度
    • 时间复杂度：insert的时间复杂度为$O(n)$，$n$为字符串的长度，StreamChecker的时间复杂度为$O(mn)$，$m$为字符串的大小，query的时间复杂度为$O(d)$，$d$为字典树的大小
    • 空间复杂度：$O(d)$