Description
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
Constraints:
1 <= words.length <= 20001 <= words[i].length <= 200words[i] consists of lowercase English letters.letter is a lowercase English letter.- At most
4 * 104 calls will be made to query.
Solutions
Solution 1
PythonJavaC++Go
class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, w: str):
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, w: List[str]) -> bool:
node = self
for c in w[::-1]:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
if node.is_end:
return True
return False
class StreamChecker:
def __init__(self, words: List[str]):
self.trie = Trie()
self.cs = []
self.limit = 201
for w in words:
self.trie.insert(w)
def query(self, letter: str) -> bool:
self.cs.append(letter)
return self.trie.search(self.cs[-self.limit :])
# Your StreamChecker object will be instantiated and called as such:
# obj = StreamChecker(words)
# param_1 = obj.query(letter)(code-box)
class Trie {
Trie[] children = new Trie[26];
boolean isEnd = false;
public void insert(String w) {
Trie node = this;
for (int i = w.length() - 1; i >= 0; --i) {
int idx = w.charAt(i) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean query(StringBuilder s) {
Trie node = this;
for (int i = s.length() - 1; i >= 0; --i) {
int idx = s.charAt(i) - 'a';
if (node.children[idx] == null) {
return false;
}
node = node.children[idx];
if (node.isEnd) {
return true;
}
}
return false;
}
}
class StreamChecker {
private StringBuilder sb = new StringBuilder();
private Trie trie = new Trie();
public StreamChecker(String[] words) {
for (String w : words) {
trie.insert(w);
}
}
public boolean query(char letter) {
sb.append(letter);
return trie.query(sb);
}
}
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker obj = new StreamChecker(words);
* boolean param_1 = obj.query(letter);
*/(code-box)
class Trie {
private:
Trie* children[26]{};
bool isEnd = false;
public:
void insert(string& w) {
Trie* node = this;
reverse(w.begin(), w.end());
for (char& c : w) {
int idx = c - 'a';
if (!node->children[idx]) {
node->children[idx] = new Trie();
}
node = node->children[idx];
}
node->isEnd = true;
}
bool search(string& w) {
Trie* node = this;
for (int i = w.size() - 1, j = 0; ~i && j < 201; --i, ++j) {
int idx = w[i] - 'a';
if (!node->children[idx]) {
return false;
}
node = node->children[idx];
if (node->isEnd) {
return true;
}
}
return false;
}
};
class StreamChecker {
public:
Trie* trie = new Trie();
string s;
StreamChecker(vector<string>& words) {
for (auto& w : words) {
trie->insert(w);
}
}
bool query(char letter) {
s += letter;
return trie->search(s);
}
};
/**
* Your StreamChecker object will be instantiated and called as such:
* StreamChecker* obj = new StreamChecker(words);
* bool param_1 = obj->query(letter);
*/(code-box)
type Trie struct {
children [26]*Trie
isEnd bool
}
func newTrie() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for i := len(word) - 1; i >= 0; i-- {
idx := word[i] - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (this *Trie) Search(word []byte) bool {
node := this
for i := len(word) - 1; i >= 0; i-- {
idx := word[i] - 'a'
if node.children[idx] == nil {
return false
}
node = node.children[idx]
if node.isEnd {
return true
}
}
return false
}
type StreamChecker struct {
trie Trie
s []byte
}
func Constructor(words []string) StreamChecker {
trie := newTrie()
for _, w := range words {
trie.Insert(w)
}
return StreamChecker{trie, []byte{}}
}
func (this *StreamChecker) Query(letter byte) bool {
this.s = append(this.s, letter)
return this.trie.Search(this.s)
}
/**
* Your StreamChecker object will be instantiated and called as such:
* obj := Constructor(words);
* param_1 := obj.Query(letter);
*/(code-box)
