745. Prefix and Suffix Search (Hard)

Given manywords,words[i]has weighti.

Design a classWordFilterthat supports one function,WordFilter.f(String prefix, String suffix). It will return the word with givenprefixandsuffixwith maximum weight. If no word exists, return -1.

Examples:

Input:
WordFilter(["apple"])
WordFilter.f("a", "e") // returns 0
WordFilter.f("b", "") // returns -1

Note:

1. words has length in range [1, 15000].
2. For each test case, up to words.length queries WordFilter.f may be made.
3. words[i] has length in range [1, 10].
4. prefix, suffix have lengths in range [0, 10].
5. words[i] and prefix, suffix queries consist of lowercase letters only.