Watch 10 video solutions for Prefix and Suffix Search, a hard level problem involving Array, Hash Table, String. This walkthrough by Algorithms Made Easy has 10,745 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive a list of words and must design a structure that returns the highest index of a word matching both a given prefix and suffix. Each query asks for f(prefix, suffix). The challenge is handling many queries efficiently while checking both ends of the word.
Approach 1: Hash Map with Pre-computed Prefix-Suffix Pairs (Preprocessing O(n * L²), Query O(1))
Precompute every possible (prefix, suffix) combination for each word and store the latest index in a hash map. For a word of length L, generate all prefixes and suffixes using nested loops and map prefix + "#" + suffix to the word index. When a query arrives, construct the same key and perform a constant-time hash lookup. The tradeoff is memory usage: preprocessing costs O(n * L²) time and space because every prefix-suffix pair is stored. The benefit is extremely fast queries. This method relies heavily on fast lookups provided by a hash table and works well when the number of queries is large.
Approach 2: Trie with Combined Prefix and Suffix Key (Build O(n * L²), Query O(L))
A more structured approach uses a Trie. For each word, insert all combinations of suffix + '#' + word into the trie. The separator ensures prefix and suffix segments remain distinguishable during traversal. Each node stores the latest index of the word passing through it. During a query, search the trie for suffix + '#' + prefix. If traversal succeeds, the stored index is the answer. This approach reduces query work to O(L) where L is the prefix/suffix length. The build phase still costs O(n * L²) because every suffix contributes multiple insertions. Tries handle overlapping strings efficiently and are common in advanced string search problems.
Approach 3: Brute Force Scan (Query O(n * L))
The simplest idea checks every word for each query. For each word, verify the prefix using a string comparison and check the suffix using substring or reverse indexing. Track the largest index that satisfies both conditions. This requires scanning all words per query, producing O(n * L) time per call and O(1) extra space. It works for very small inputs but fails when the number of queries grows.
Recommended for interviews: The trie-based design is the approach most interviewers expect because it demonstrates understanding of efficient string indexing and custom data structures. Explaining the brute force solution first shows baseline reasoning. Then moving to a trie or precomputed hash map demonstrates the optimization needed for repeated queries.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * L) per query | O(1) | Small inputs or quick prototype without preprocessing |
| Hash Map with Precomputed Prefix-Suffix | Build: O(n * L²), Query: O(1) | O(n * L²) | Best when query count is very high and memory is acceptable |
| Trie with Combined Prefix-Suffix Key | Build: O(n * L²), Query: O(L) | O(n * L²) | Interview-friendly design for fast prefix/suffix lookups |