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
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.