Design an algorithm that accepts a stream of characters and checks if a suffix of these characters is a string of a given array of strings words.
For example, if words = ["abc", "xyz"] and the stream added the four characters (one by one) 'a', 'x', 'y', and 'z', your algorithm should detect that the suffix "xyz" of the characters "axyz" matches "xyz" from words.
Implement the StreamChecker class:
StreamChecker(String[] words) Initializes the object with the strings array words.
boolean query(char letter) Accepts a new character from the stream and returns true if any non-empty suffix from the stream forms a word that is in words.
Example 1:
Input
["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"]]
Output
[null, false, false, false, true, false, true, false, false, false, false, false, true]
Explanation
StreamChecker streamChecker = new StreamChecker(["cd", "f", "kl"]);
streamChecker.query("a"); // return False
streamChecker.query("b"); // return False
streamChecker.query("c"); // return False
streamChecker.query("d"); // return True, because 'cd' is in the wordlist
streamChecker.query("e"); // return False
streamChecker.query("f"); // return True, because 'f' is in the wordlist
streamChecker.query("g"); // return False
streamChecker.query("h"); // return False
streamChecker.query("i"); // return False
streamChecker.query("j"); // return False
streamChecker.query("k"); // return False
streamChecker.query("l"); // return True, because 'kl' is in the wordlist
classTrie:def__init__(self):self.children=[None]*26self.is_end=Falsedefinsert(self,w:str):node=selfforcinw[::-1]:idx=ord(c)-ord('a')ifnode.children[idx]isNone:node.children[idx]=Trie()node=node.children[idx]node.is_end=Truedefsearch(self,w:List[str])->bool:node=selfforcinw[::-1]:idx=ord(c)-ord('a')ifnode.children[idx]isNone:returnFalsenode=node.children[idx]ifnode.is_end:returnTruereturnFalseclassStreamChecker:def__init__(self,words:List[str]):self.trie=Trie()self.cs=[]self.limit=201forwinwords:self.trie.insert(w)defquery(self,letter:str)->bool:self.cs.append(letter)returnself.trie.search(self.cs[-self.limit:])# Your StreamChecker object will be instantiated and called as such:# obj = StreamChecker(words)# param_1 = obj.query(letter)
classTrie{Trie[]children=newTrie[26];booleanisEnd=false;publicvoidinsert(Stringw){Trienode=this;for(inti=w.length()-1;i>=0;--i){intidx=w.charAt(i)-'a';if(node.children[idx]==null){node.children[idx]=newTrie();}node=node.children[idx];}node.isEnd=true;}publicbooleanquery(StringBuilders){Trienode=this;for(inti=s.length()-1;i>=0;--i){intidx=s.charAt(i)-'a';if(node.children[idx]==null){returnfalse;}node=node.children[idx];if(node.isEnd){returntrue;}}returnfalse;}}classStreamChecker{privateStringBuildersb=newStringBuilder();privateTrietrie=newTrie();publicStreamChecker(String[]words){for(Stringw:words){trie.insert(w);}}publicbooleanquery(charletter){sb.append(letter);returntrie.query(sb);}}/** * Your StreamChecker object will be instantiated and called as such: * StreamChecker obj = new StreamChecker(words); * boolean param_1 = obj.query(letter); */
classTrie{private:Trie*children[26]{};boolisEnd=false;public:voidinsert(string&w){Trie*node=this;reverse(w.begin(),w.end());for(char&c:w){intidx=c-'a';if(!node->children[idx]){node->children[idx]=newTrie();}node=node->children[idx];}node->isEnd=true;}boolsearch(string&w){Trie*node=this;for(inti=w.size()-1,j=0;~i&&j<201;--i,++j){intidx=w[i]-'a';if(!node->children[idx]){returnfalse;}node=node->children[idx];if(node->isEnd){returntrue;}}returnfalse;}};classStreamChecker{public:Trie*trie=newTrie();strings;StreamChecker(vector<string>&words){for(auto&w:words){trie->insert(w);}}boolquery(charletter){s+=letter;returntrie->search(s);}};/** * Your StreamChecker object will be instantiated and called as such: * StreamChecker* obj = new StreamChecker(words); * bool param_1 = obj->query(letter); */
typeTriestruct{children[26]*TrieisEndbool}funcnewTrie()Trie{returnTrie{}}func(this*Trie)Insert(wordstring){node:=thisfori:=len(word)-1;i>=0;i--{idx:=word[i]-'a'ifnode.children[idx]==nil{node.children[idx]=&Trie{}}node=node.children[idx]}node.isEnd=true}func(this*Trie)Search(word[]byte)bool{node:=thisfori:=len(word)-1;i>=0;i--{idx:=word[i]-'a'ifnode.children[idx]==nil{returnfalse}node=node.children[idx]ifnode.isEnd{returntrue}}returnfalse}typeStreamCheckerstruct{trieTries[]byte}funcConstructor(words[]string)StreamChecker{trie:=newTrie()for_,w:=rangewords{trie.Insert(w)}returnStreamChecker{trie,[]byte{}}}func(this*StreamChecker)Query(letterbyte)bool{this.s=append(this.s,letter)returnthis.trie.Search(this.s)}/** * Your StreamChecker object will be instantiated and called as such: * obj := Constructor(words); * param_1 := obj.Query(letter); */