题目描述

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/stream-of-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

解法一：暴力法
使用StringBuffer构造不断加入一个letter字符后的字符串
然后用String类的endswith（）方法判断字符串是否以words字符串结尾

代码

class StreamChecker {String[] strings=null;StringBuffer sb = null;public StreamChecker(String[] words) {this.strings=words;this.sb = new StringBuffer();}public boolean query(char letter) {sb.append(letter);String collect = sb.toString();for(String s:strings){if(collect.endsWith(s)){return true;}}return false;}
}

解放二：前缀树
使用StringBuffer构造不断加入一个letter字符后的字符串
将words数组的字符串反转后插入前缀树，然后反转StringBuffer字符串与前缀树中相比较

代码

class Trie{/* Trie树节点* 假设我们只做26个小写字母下的匹配*/public static class Node{//当前节点值private char value;//当前节点的孩子节点private Node[] childNode;//标志当前节点是否是某单词结尾private boolean isTail;public Node(char value) {this.value = value;}}//初始化	Node root;public void init() {root = new Node('\\0');root.childNode = new Node[26];}/* 将当前串插入字典树* @param chars*/public void insertStr(char[] chars) {//首先判断首字符是否已经在字典树中，然后判断第二字符，依次往下进行判断，找到第一个不存在的字符进行插入孩节点Node p = root;//表明当前处理到了第几个字符int chIndex = 0;while (chIndex < chars.length) {while (chIndex < chars.length && null != p) {Node[] children = p.childNode;boolean find = false;//遍历子节点，确定该字符是否是其中一个子节点的valuefor (Node child : children) {if (null == child) {continue;}if (child.value == chars[chIndex]) {//当前字符已经存在，不需要再进行存储//从当前节点出发，存储下一个字符p = child;++ chIndex;find = true;break;}}if (Boolean.TRUE.equals(find)) {//在孩子中找到了 不用再次存储break;}//如果把孩子节点都找遍了，还没有找到这个字符，直接将这个字符加入当前节点的孩子节点Node node = new Node(chars[chIndex]);node.childNode = new Node[26];children[chars[chIndex] - 'a'] = node;p = node;++ chIndex;}}//字符串中字符全部进入tire树中后，将最后一个字符所在节点标志为结尾节点p.isTail = true;}public boolean query(StringBuilder s){Node p = root;for(int i=s.length()-1,j=0;i>=0&&j<201;--i,++j){int count=0;//count计算一个字符的比较次数，如果count=26代表比较完26个子节点都没找到，返回falsechar idex = s.charAt(i);Node[] children = p.childNode;//遍历子节点for(Node child:children){if(child==null){count++;continue;}//发现字符与一个子节点的value相等，则定位到下个字符与该子节点的子节点进行比较if(child.value==idex){p=child;//发现是一个word[]中的字符串，匹配成功返回trueif(p.isTail==true){return true;}break;//跳出当前的子节点遍历}else{count++;}}if(count==26){return false;}}return false;}
}class StreamChecker {private StringBuilder sb = new StringBuilder();private Trie trie = new Trie();public StreamChecker(String[] words) {trie.init();for (String w : words) {StringBuffer sb = new StringBuffer(w);trie.insertStr(sb.reverse().toString().toCharArray());}}public boolean query(char letter) {sb.append(letter);return trie.query(sb);}
}

关于前缀树请参考链接: link