This approach utilizes a reversed Trie (prefix tree) to efficiently manage and query suffixes of input characters. By storing the reversed words in a Trie, we can match suffixes of the input stream by querying from the current character backwards. For each character queried, we move through the Trie from those characters up to a certain limit (or until no further match) to see if any of the suffixes match one of the stored words.
Time Complexity for insertion: O(N*L), where N is the number of words and L is the maximum length of a word.
Time Complexity for queries: O(Q*L) where Q is the number of queries and L is the maximum length of a word.
Space Complexity: O(N*L) for storing the words in the Trie.
1class TrieNode:
2 def __init__(self):
3 self.children = {}
4 self.is_end_of_word = False
5
6class StreamChecker:
7 def __init__(self, words):
8 self.root = TrieNode()
9 self.stream = []
10 for word in words:
11 node = self.root
12 for char in reversed(word):
13 if char not in node.children:
14 node.children[char] = TrieNode()
15 node = node.children[char]
16 node.is_end_of_word = True
17
18 def query(self, letter):
19 self.stream.append(letter)
20 node = self.root
21 for char in reversed(self.stream):
22 if node.is_end_of_word:
23 return True
24 if char not in node.children:
25 return False
26 node = node.children[char]
27 return node.is_end_of_wordThe implementation involves creating a Trie that stores each word in reverse. When a query is made, characters are added to a list representing the current stream. We then check from the current end of the stream backwards through the Trie to determine if any suffix matches a word.
The Aho-Corasick algorithm is useful for searching multiple 'dictionary' words within a text. We build an automaton with all words and query the stream letters. This data structure enables matching of all dictionary words in parallel through a finite state machine that jumps quickly between states even upon mismatches.
Time Complexity for building: O(N*L), because we insert and construct failure links.
Time Complexity for queries: O(Q*L) leveraging finite state machine transitions.
Space Complexity: O(N*L) due to the state-space storage representing words.
1class TrieNode {
2 constructor() {
3 this.children = {};
4 this.isEndOfWord = false;
5 this.fail = null;
6 }
7}
8
9class StreamChecker {
10 constructor(words) {
11 this.root = new TrieNode();
12 this.node = this.root;
13 // Insert all words
14 for (let word of words) {
15 let node = this.root;
16 for (let i = word.length - 1; i >= 0; i--) {
17 const char = word[i];
18 if (!(char in node.children)) {
19 node.children[char] = new TrieNode();
20 }
21 node = node.children[char];
22 }
23 node.isEndOfWord = true;
24 }
25 // Build fail links
26 const q = [this.root];
27 while (q.length) {
28 const current = q.shift();
29 for (let char in current.children) {
30 let child = current.children[char];
31 let failNode = current.fail;
32 while (failNode && !(char in failNode.children)) {
33 failNode = failNode.fail;
34 }
35 if (failNode) {
36 child.fail = failNode.children[char];
37 } else {
38 child.fail = this.root;
39 }
40 child.isEndOfWord = child.isEndOfWord || (child.fail && child.fail.isEndOfWord);
41 q.push(child);
42 }
43 }
44 }
45
46 query(letter) {
47 while (this.node && !(letter in this.node.children)) {
48 this.node = this.node.fail;
49 }
50 if (this.node) {
51 this.node = this.node.children[letter];
52 } else {
53 this.node = this.root;
54 }
55 return this.node ? this.node.isEndOfWord : false;
56 }
57}
58The JavaScript version also uses the Aho-Corasick automaton. We have created trie nodes, inserted the words in reverse, and then built failure links between nodes to allow for fast lookup during the query.