490. Prefix and Suffix Search
Design a dictionary that can be searched by prefix and suffix at the same time.
Implement a class WordFilter:
WordFilter(words)— the constructor receives a list of lowercase words. Words may repeat.f(pref, suff)— returns the largest indexisuch thatwords[i]starts withprefand ends withsuff. If no word qualifies, return-1.
The constructor runs once, but f may be called many times — so it pays to move work into the constructor and make each query cheap. Note that pref and suff are allowed to overlap inside a short word: the word "ab" both starts with "ab" and ends with "ab".
Example 1:
Input: WordFilter(["apple"]); f("a", "e")
Output: 0
Explanation: "apple" starts with "a" and ends with "e", so index 0 is the answer.
Example 2:
Input: WordFilter(["banana", "band", "bandana"]); f("ban", "ana"); f("ban", "d"); f("x", "a")
Output: 2, then 1, then -1
Explanation: f("ban", "ana"): both "banana" (0) and "bandana" (2) qualify — return the larger index, 2. f("ban", "d"): only "band" (1). f("x", "a"): nothing starts with "x", so -1.
Constraints:
- 1 ≤ words.length ≤ 10⁴
- 1 ≤ words[i].length ≤ 7
- 1 ≤ pref.length, suff.length ≤ 7
- words[i], pref, and suff consist of lowercase English letters only
- At most 10⁴ calls to f.
Hints:
The naive f scans all words checking startswith/endswith. Correct, but every query pays O(n · L) — think about what you could precompute once in the constructor instead.
Words are at most 7 letters, so each word has at most 7 × 7 = 49 (prefix, suffix) combinations. Precompute them all into a hash map keyed by the pair; inserting in index order means later words overwrite earlier ones with a larger index for free.
The trie version: for every suffix s of a word w, insert the string s + "#" + w into one trie, stamping the word's index on each node you touch. Then f(pref, suff) is a single walk down suff + "#" + pref.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: WordFilter(["apple"]); f("a", "e")
Expected output: 0