745. 前缀和后缀搜索

Difficulty
Hard
Tags
前缀树
URL
https://leetcode.cn/problems/prefix-and-suffix-search/
Star
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
实现 WordFilter 类：
  • WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
  • f(string pref, string suff) 返回词典中具有前缀 prefix 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 1 。
示例：
输入
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
输出
[null, 0]
解释
WordFilter wordFilter = new WordFilter(["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 次调用
通过次数19,079提交次数44,115

前缀树

思路
建立两棵树，分别存放前缀和后缀，然后每个节点存放着以改前缀为前缀的单词的下标。这样当搜索前缀和后缀时，得到了两个列表，然后用双指针来找共同的最大的值。
题解
class Node:
    def __init__(self):
        self.child = dict()
        self.word_list = list()

class Trie:
    def __init__(self):
        self.root = Node()
    
    def insert(self, word, idx):
        node = self.root
        for char in word:
            if char not in node.child:
                node.child[char] = Node()
            node = node.child[char]
            node.word_list.append(idx)


    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.child:
                return []
            node = node.child[char]
        
        return node.word_list


class WordFilter:

    def __init__(self, words: List[str]):
        self.t1 = Trie()
        self.t2 = Trie()

        for i, w in enumerate(words):
            self.t1.insert(w, i)
            self.t2.insert(w[::-1], i)

    def f(self, pref: str, suff: str) -> int:
        a = self.t1.search(pref)
        b = self.t2.search(suff[::-1])
        if len(a) == 0 or len(b) == 0:
            return -1
            
        res = -1
        p1, p2 = len(a)-1, len(b)-1
        while p1 >= 0 and p2 >= 0:
            if a[p1] == b[p2]:
                res = a[p1]
                break
            elif a[p1] > b[p2]:
                p2 -= 1
            else:
                p1 -= 1

        return res
            
        



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