# 745. Prefix and Suffix Search Given many `words`, `words[i]` has weight `i`. Design a class `WordFilter` that supports one function, `WordFilter.f(String prefix, String suffix)`. It will return the word with given `prefix` and `suffix` with 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. 对一系列词查询满足给定前缀和后缀的词的最大index。查词用Trie。但把每个可能的前缀和后缀的组合都放进trie空间会非常大。利用Trie找前缀很方便的性质，把单词不同后缀和整个单词拼在一起组成不同的新词放trie里，这样就不用针对所有可能的前缀单独放了。 代码参考自[花花](https://link.zhihu.com/?target=https%3A//www.youtube.com/watch%3Fv%3Da-4WbFqalIA)。 ```cpp /* * @lc app=leetcode id=745 lang=cpp * * [745] Prefix and Suffix Search * * https://leetcode.com/problems/prefix-and-suffix-search/description/ * * algorithms * Hard (31.50%) * Likes: 237 * Dislikes: 165 * Total Accepted: 14.2K * Total Submissions: 44.6K * Testcase Example: '["WordFilter","f"]\n[[["apple"]],["a","e"]]' * * Given many words, words[i] has weight i. * * Design a class WordFilter that supports one function, WordFilter.f(String * prefix, String suffix). It will return the word with given prefix and suffix * with maximum weight. If no word exists, return -1. * * Examples: * * * Input: * WordFilter(["apple"]) * WordFilter.f("a", "e") // returns 0 * WordFilter.f("b", "") // returns -1 * * * * * Note: * * * words has length in range [1, 15000]. * For each test case, up to words.length queries WordFilter.f may be made. * words[i] has length in range [1, 10]. * prefix, suffix have lengths in range [0, 10]. * words[i] and prefix, suffix queries consist of lowercase letters only. * * * * */ // @lc code=start class WordFilter { public: class TrieNode { public: vector children; bool word; int index; TrieNode(int ind): children(27, nullptr), word(false), index(ind) {} }; TrieNode *root; void insert(const string &w, int index) { auto cur = root; for (const auto c : w) { const int i = c - 'a'; if (cur->children[i] == nullptr) cur->children[i] = new TrieNode(index); cur = cur->children[i]; cur->index = index; } cur->word = true; } TrieNode* find(const string &prefix) { auto cur = root; for (const auto c : prefix) { cur = cur->children[c - 'a']; if (cur == nullptr) break; } return cur; } int query(const string &prefix) { auto cur = find(prefix); if (cur == nullptr) return -1; return cur->index; } WordFilter(vector& words) { root = new TrieNode(-1); for (int i = 0; i < words.size(); ++i) { const auto &w = words[i]; auto key = "{" + w; insert(key, i); for (int j = 0; j < w.size(); ++j) { key = w[w.size() - j - 1] + key; insert(key, i); } } } int f(string prefix, string suffix) { return query(suffix + "{" + prefix); } }; /** * Your WordFilter object will be instantiated and called as such: * WordFilter* obj = new WordFilter(words); * int param_1 = obj->f(prefix,suffix); */ // @lc code=end ``` ```python # Given many words, words[i] has weight i. # # Design a class WordFilter that supports one function, WordFilter.f(String pre # fix, String suffix). It will return the word with given prefix and suffix with m # aximum weight. If no word exists, return -1. # # Examples: # # # Input: # WordFilter(["apple"]) # WordFilter.f("a", "e") // returns 0 # WordFilter.f("b", "") // returns -1 # # # # # Note: # # # words has length in range [1, 15000]. # For each test case, up to words.length queries WordFilter.f may be made. # words[i] has length in range [1, 10]. # prefix, suffix have lengths in range [0, 10]. # words[i] and prefix, suffix queries consist of lowercase letters only. # # # # Related Topics Trie # leetcode submit region begin(Prohibit modification and deletion) class WordFilter(object): class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.trie = {} def insert(self, word, i): """ Inserts a word into the trie. :type word: str :rtype: dict """ cur = self.trie for c in word: if c not in cur: cur[c] = {} cur = cur[c] cur['i'] = i return cur def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: int """ cur = self.trie for c in prefix: if c not in cur: return -1 cur = cur[c] return cur['i'] def __init__(self, words): """ :type words: List[str] """ self.trie = WordFilter.Trie() for weight, word in enumerate(words): t = self.trie t.insert(',' + word, weight) for i in range(len(word)): w = word[-i:] t.insert(w + ',' + word, weight) def f(self, prefix, suffix): """ :type prefix: str :type suffix: str :rtype: int """ return self.trie.startsWith(suffix + ',' + prefix) # Your WordFilter object will be instantiated and called as such: # obj = WordFilter(words) # param_1 = obj.f(prefix,suffix) # leetcode submit region end(Prohibit modification and deletion) ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://hao-fu-1.gitbook.io/oj/trie/745.-prefix-and-suffix-search.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.