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