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
2import java.util.HashMap;
3import java.util.Map;
4
5class WordFilter {
6
7 private final Map<String, Integer> map;
8
9 public WordFilter(String[] words) {
10 map = new HashMap<>();
11 for (int weight = 0; weight < words.length; weight++) {
12 String word = words[weight];
13 int len = word.length();
14 for (int i = 0; i <= len; i++) {
15 for (int j = 0; j <= len; j++) {
16 String prefix = word.substring(0, i);
17 String suffix = word.substring(j, len);
18 map.put(prefix + "#" + suffix, weight);
19 }
20 }
21 }
22 }
23
24 public int f(String pref, String suff) {
25 return map.getOrDefault(pref + "#" + suff, -1);
26 }
27}This Java solution utilizes a map to store the indices of words by every possible combination of prefix and suffix keys, formed by joining the prefix and suffix with a delimiter '#'. When f() is called, the map is queried with the corresponding combined 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.