题目
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。
示例
输入
[“WordFilter”, “f”]
[[[“apple”]], [“a”, “e”]]
输出
[null, 0]
解释
WordFilterwordFilter=newWordFilter([“apple”]);wordFilter.f(“a”, “e”); // 返回 0 ，因为下标为 0 的单词：前缀 prefix = “a” 且 后缀 suff = “e” 。
提示：
1 <= words.length <= 104
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i]、pref 和 suff 仅由小写英文字母组成
最多对函数 f 执行 104 次调用
思路
- 维护两个字典树，一个记录前缀，另一个记录后缀。这里注意：每个节点需定义一个集合变量，记录给定words中以该节点之前字符串为前缀的下标。
- 分别得到前缀和后缀的下标集合，二者都从后往前遍历，比较二者大小，若相等直接返回下标，前缀中坐标大则前缀往前，后缀中坐标大则后缀往前。
题解
# 字典树代码 class TireNode: def __init__(self): # 记录字符串下标 self.id = [] self.child = [None] * 26 # 插入 def insert(self, s, index, root): if root is None: return None for i in list(s): if root.child[ord(i) - ord('a')] is None: root.child[ord(i) - ord('a')] = TireNode() root = root.child[ord(i) - ord('a')] # 加入下标 root.id.append(index) # 寻找前缀的下标集合 def search(self, s, root): if root is None: return None for i in list(s): if root.child[ord(i) - ord('a')] is None: return None root = root.child[ord(i) - ord('a')] return root.id class WordFilter: def __init__(self, words: List[str]): self.TreeQ = TireNode() self.TreeH = TireNode() # 初始化两树 for i in range(len(words)): self.TreeQ.insert(words[i], i, self.TreeQ) self.TreeH.insert(words[i][::-1], i, self.TreeH) def f(self, pref: str, suff: str) -> int: # 分别找到前缀和后缀对应的下标集合 Q = self.TreeQ.search(pref, self.TreeQ) H = self.TreeH.search(suff[::-1], self.TreeH) # 任意一个为空直接返回 if H is None or Q is None: return -1 l, r = len(Q) - 1, len(H) -1 # 从后往前遍历 while l >= 0 and r >= 0: if Q[l] == H[r]: return Q[l] elif Q[l] > H[r]: l -= 1 else: r -= 1 return -1
