https://leetcode.com/problems/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".
Constraints:
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']