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
2#include <vector>
3#include <string>
4#include <unordered_map>
5using namespace std;
6
class WordFilter {
unordered_map<string, int> map;
public:
WordFilter(vector<string>& words) {
int n = words.size();
for (int i = 0; i < n; ++i) {
string word = words[i];
int len = word.size();
for (int p = 0; p <= len; ++p) {
for (int s = 0; s <= len; ++s) {
string key = word.substr(0, p) + "#" + word.substr(s);
map[key] = i;
}
}
}
}
int f(string pref, string suff) {
string key = pref + "#" + suff;
if (map.find(key) != map.end())
return map[key];
return -1;
}
};In this C++ solution, a hash map is used where each key is formed by concatenating every possible prefix and suffix of each word, using a delimiter '#'. These keys are mapped to the index of the words. Querying involves checking if the prefix-suffix combined key exists in the hash map.