745. Prefix and Suffix Search


Design a special dictionary with some words that searchs 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. 	
f(string prefix, string suffix) Returns __the index of the word in the dictionary,__ which has the prefix prefix and the suffix suffix. If there is more than one valid index, return **the largest** of them. If there is no such word in the dictionary, return -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".


1 <= words.length <= 15000 	
1 <= words[i].length <= 10 	
1 <= prefix.length, suffix.length <= 10 	
words[i], prefix and suffix consist of lower-case English letters only. 	
At most 15000 calls will be made to the function f.

  • code
class WordFilter:

    def __init__(self, words: List[str]):
        self.trie = {}
        for index, word in enumerate(words):
            for i in range(len(word) + 1):
                node = self.trie
                word_to_insert = word[i:] + '#' + word
                for c in word_to_insert:
                    if c not in node:
                        node[c] = {}
                    node = node[c]
                    node['res'] = index

    def f(self, prefix: str, suffix: str) -> int:
        node = self.trie
        for c in suffix + '#' + prefix:
            if c not in node:
                return -1
            node = node[c]
        return node['res']