Prefix and Suffix Search — LeetCode 745 Python Solution

The problem

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.

Example

Input

["WordFilter", "f"]

Output

[null, 0]

Explanation

WordFilter wordFilter = new WordFilter(["apple"]);

Python solution

class WordFilter:
    def __init__(self, words: List[str]):
        self.d = {}
        for k, w in enumerate(words):
            n = len(w)
            for i in range(n + 1):
                a = w[:i]
                for j in range(n + 1):
                    b = w[j:]
                    self.d[(a, b)] = k

    def f(self, pref: str, suff: str) -> int:
        return self.d.get((pref, suff), -1)


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

Complexity

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 745. Prefix and Suffix Search is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems