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.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.
This 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.
Java
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.
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.
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.
JavaScript
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.
| Approach | Complexity |
|---|---|
| Trie with Combined Prefix and Suffix Key | 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. |
| Hash Map with Pre-computed Indices | 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. |
Implement Trie (Prefix Tree) - Leetcode 208 • NeetCode • 242,050 views views
Watch 9 more video solutions →Practice Prefix and Suffix Search with our built-in code editor and test cases.
Practice on FleetCode