Design a special dictionary that searches the words in it by a prefix and a suffix.
Implement the WordFilter class:
WordFilter(string[] words) Initializes the object with the words in the dictionary.f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return -1.Example 1:
Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".
Constraints:
1 <= words.length <= 1041 <= words[i].length <= 71 <= pref.length, suff.length <= 7words[i], pref and suff consist of lowercase English letters only.104 calls will be made to the function f.#745 Prefix and Suffix Search requires designing a data structure that efficiently returns the index of a word matching both a given prefix and suffix. A naive approach would check every word for each query, but that leads to poor performance for large datasets.
The key insight is to use a Trie-based design. One effective technique is to insert combinations of suffix + '#' + word into a Trie. This allows prefix and suffix constraints to be merged into a single searchable string. During queries, you search for suffix + '#' + prefix and retrieve the stored index representing the latest matching word.
This approach precomputes searchable patterns during construction, enabling fast lookups. While preprocessing may take extra memory and time, it significantly improves query performance. With optimized insertion and lookup in the Trie, queries become very efficient, making this approach suitable for interview-level design problems involving string indexing.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Check | Query: O(N * L) | O(1) |
| Trie with Suffix#Prefix Combination | Build: O(N * L^2), Query: O(L) | O(N * L^2) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Take "apple" as an example, we will insert add "apple{apple", "pple{apple", "ple{apple", "le{apple", "e{apple", "{apple" into the Trie Tree.
If the query is: prefix = "app", suffix = "le", we can find it by querying our trie for "le { app".
We use '{' because in ASCii Table, '{' is next to 'z', so we just need to create new TrieNode[27] instead of 26. Also, compared with traditional Trie, we add the attribute weight in class TrieNode. You can still choose any different character.
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;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem are common in FAANG-style interviews. It tests knowledge of Trie data structures, string manipulation, and designing efficient search systems, which are important concepts in large-scale systems.
A Trie (prefix tree) is the most suitable data structure for this problem because it efficiently handles prefix-based lookups. By cleverly combining suffix and prefix into a single searchable key, the Trie can answer queries in near O(L) time where L is the length of the query.
The optimal approach typically uses a Trie that stores combinations of suffix and prefix patterns. By inserting strings like suffix + '#' + word into the Trie, queries can search for suffix + '#' + prefix directly. This allows fast lookups while maintaining efficient indexing of words.
The difficulty comes from the need to support fast queries while handling both prefix and suffix constraints simultaneously. Efficient solutions require creative data structure design, such as combining strings and building specialized Trie indexes.
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.