Sponsored
Sponsored
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(
The 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.