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 TrieNode[] children = new TrieNode[26];
3 boolean isEndOfWord = false;
4}
5
6class StreamChecker {
7 TrieNode root = new TrieNode();
8 StringBuilder stream = new StringBuilder();
9
10 public StreamChecker(String[] words) {
11 for (String word : words) {
12 TrieNode node = root;
13 for (int i = word.length() - 1; i >= 0; i--) {
14 char c = word.charAt(i);
15 if (node.children[c - 'a'] == null) {
16 node.children[c - 'a'] = new TrieNode();
17 }
18 node = node.children[c - 'a'];
19 }
20 node.isEndOfWord = true;
21 }
22 }
23
24 public boolean query(char letter) {
25 stream.append(letter);
26 TrieNode node = root;
27 for (int i = stream.length() - 1; i >= 0; i--) {
28 char c = stream.charAt(i);
29 if (node.children[c - 'a'] == null) {
30 return false;
31 }
32 node = node.children[c - 'a'];
33 if (node.isEndOfWord) {
34 return true;
35 }
36 }
37 return false;
38 }
39}The Java implementation similarly uses a Trie data structure, where each character is a child node and the entire word is stored in reverse. Each query checks the current character and its suffix for possible matches by traversing backwards in the stream string builder.
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.