745. Prefix and Suffix Search

Hard

50 Points

Array

Hash Table

String

Design

Trie

Design a special dictionary that searches the words in it by a prefix and a suffix. Implement the WordFilter class:

Examples

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 <= 104
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i], pref and suff consist of lowercase English letters only.
At most 104 calls will be made to the function f.