745 前缀和后缀搜索（Trie树-构造）

短命女 2022-09-10 10:12 110阅读 0赞

**1. 问题描述：**

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。  
实现 WordFilter 类：  
WordFilter(string\[\] words) 使用词典中的单词 words 初始化对象。  
f(string prefix, string suffix) 返回词典中具有前缀 prefix 和后缀suffix 的单词的下标。如果存在不止一个满足要求的下标，返回其中最大的下标 。如果不存在这样的单词，返回 -1 。

**示例**

输入：  
\["WordFilter", "f"\]  
\[\[\["apple"\]\], \["a", "e"\]\]  
输出：  
\[null, 0\]  
解释：  
WordFilter wordFilter = new WordFilter(\["apple"\]);  
wordFilter.f("a", "e"); // 返回 0 ，因为下标为 0 的单词的 prefix = "a" 且 suffix = 'e" 。

**提示：**

1 <= words.length <= 15000  
1 <= words\[i\].length <= 10  
1 <= prefix.length, suffix.length <= 10  
words\[i\]、prefix 和 suffix 仅由小写英文字母组成  
最多对函数 f 进行 15000 次调用  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/prefix-and-suffix-search

**2. 思路分析：**

这道题目的思路其实比较难想，需要使用到**构造**的方法，当我们构造出来之后那么实现就比较简单了；我们其实是将所有单词的后缀 + "\#" + 前缀插入到Trie树中，举一个例子：当我们插入一个单词"abcde"，其实是插入下面的单词到Trie树中：

\#abcde  
e\#abcde  
de\#abcde  
cde\#abcde  
bcde\#abcde  
abcde\#abcde

我们在查找前缀"a"和后缀"de"的时候可以查找前缀de\#a是否存在即可，可以发现在Trie树中是存在当前前缀的，其实想到这个思路之后就比较好实现了，都是Trie树的插入单词与查找前缀的操作。

**3. 代码如下：**

from typing import List
    
    
    class WordFilter:
        # 将所有后缀放在前面 + "#" + 前缀插入到Trie树中
        def __init__(self, words: List[str]):
            # n是一个经验值, 其实在Trie树中的前缀都是可以重复使用的所以并不需要创建这么多的节点
            n = 200000
            # Trie树中的节点
            son = [[0] * 27 for i in range(n)]
            # 用来记录前缀的最大权重
            w = [0] * n
            self.son = son
            self.w = w
            # 唯一标识Trie树中的节点编号
            self.idx = 1
            # 插入所有构造出来的单词
            for i in range(len(words)):
                _s = "#" + words[i]
                self.insert(_s, i)
                # 插入拼接之后的后缀 + "#" + 前缀
                for j in range(len(words[i]) - 1, -1, -1):
                    s = words[i]
                    self.insert(s[j: len(s)] + _s, i)
    
        # 在Trie树中插入当前的单词, _id表示当前单词的编号, 这样可以更新当前前缀的最大编号
        def insert(self, word: str, _id: int):
            son = self.son
            w = self.w
            p = 0
            for c in word:
                # 当当前字符为"#"为26
                t = 26
                if c != "#": t = ord(c) - ord("a")
                if son[p][t] == 0:
                    son[p][t] = self.idx
                    self.idx += 1
                p = son[p][t]
                # 更新当前前缀的最大下标
                w[p] = _id
    
        def query(self, w: str):
            p = 0
            son = self.son
            for c in w:
                t = 26
                if c != "#":
                    t = ord(c) - ord("a")
                if son[p][t] == 0: return -1
                p = son[p][t]
            return self.w[p]
    
        def f(self, prefix: str, suffix: str) -> int:
            return self.query(suffix + "#" + prefix)