Sponsored
Sponsored
This approach leverages the use of a Trie (prefix tree), where each node can store a unique combination of prefix and suffix of words. By combining prefixes and suffixes into a single key when inserting the words and when querying, one can efficiently determine if a word with a given prefix and suffix exists.
Time complexity is O(W^2) for initialization where W is the average length of words. Query time complexity is O(P + S), where P and S are the lengths of the prefix and suffix respectively. Space complexity is O(W^2 * N) for the Trie, where N is the number of words.
1
2class TrieNode:
3 def __init__(self):
4 self.children = {}
5 self.weight = -1
6
7
8class WordFilter:
9 def __init__(self, words):
10 self.trie = TrieNode()
11 for weight, word in enumerate(words):
12 long_word = word + '#' + word
13 for j in range(len(word)+1):
14 curr = self.trie
15 curr.weight = weight
16 for c in long_word[j:]:
17 if c not in curr.children:
18 curr.children[c] = TrieNode()
19 curr = curr.children[c]
20 curr.weight = weight
21
22 def f(self, pref, suff):
23 curr = self.trie
24 search_word = suff + '#' + pref
25 for char in search_word:
26 if char not in curr.children:
27 return -1
28 curr = curr.children[char]
29 return curr.weight
30This Python solution constructs a Trie where each possible prefix-suffix combination maps to the index of the most recently added word with that combination. When querying with a prefix and a suffix, the function builds a search key by appending the suffix, a delimiter '#', and the prefix, and traverses the Trie according to this composite key.
This approach involves storing each word’s prefix and suffix combinations in a hash map, along with its index. During query operations, the hash map is used to look up the word using a prefix and suffix combination.
Time complexity is O(W^2 * N) for preprocessing and O(1) for query. Space complexity is O(W^2 * N), where W is the word length and N is the number of words.
1
2class WordFilter {
3 constructor
This Javascript implementation uses a Map to store indices against concatenated keys formed from each word's prefix and suffix combinations. Querying checks if such a key exists in the map and returns the stored index.