#745

Prefix and Suffix Search

master · 1700 · lc hard +32 · 40.8% accepted · 2,346 likes · top 20%

Description

Build a dictionary that supports simultaneous prefix and suffix lookups.

Implement the WordFilter class:

- WordFilter(string[] words) Loads the words into the dictionary (0-indexed).

- f(string pref, string suff) Returns the largest index of a word that starts with pref and ends with suff. If no match exists, returns -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".

Code

class WordFilter:

    def __init__(self, words: List[str]):
        

    def f(self, pref: str, suff: str) -> int:
        


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)

class WordFilter:

    def __init__(self, words: List[str]):
        

    def f(self, pref: str, suff: str) -> int:
        


# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)