discuz 企业网站 模板,建立一个网站平台需要多少钱,游戏代理怎么赚钱的,网站名字怎样做版权字符流【LC1032】 设计一个算法#xff1a;接收一个字符流#xff0c;并检查这些字符的后缀是否是字符串数组 words 中的一个字符串。 例如#xff0c;words [abc, xyz] 且字符流中逐个依次加入 4 个字符 a、x、y 和 z #xff0c;你所设计的算法…字符流【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)O(n)O(n)nnn为字符串的长度StreamChecker的时间复杂度为O(mn)O(mn)O(mn)mmm为字符串的大小query的时间复杂度为O(d)O(d)O(d)ddd为字典树的大小空间复杂度O(d)O(d)O(d)
