1.题目基本信息

1.1.题目描述

设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。

实现 WordFilter 类：

• WordFilter(string[] words) 使用词典中的单词 words 初始化对象。

• f(string pref, string suff) 返回词典中具有前缀 pref 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标，返回其中 最大的下标 。如果不存在这样的单词，返回 -1 。

1.2.题目地址

https://leetcode.cn/problems/prefix-and-suffix-search/description/

2.解题方法

2.1.解题思路

字典树

3.解题代码

python代码

class Trie():
    def __init__(self):
        self.sons = {}
        self.wordIdxs = []
        self.end = False
    
    def insert(self, word:str, idx:int):
        cur = self
        # cur.wordIdxs.append(idx)
        for c in word:
            if c not in cur.sons:
                cur.sons[c] = Trie()
            cur = cur.sons[c]
            cur.wordIdxs.append(idx)
        cur.end = True
    
    def find(self, word:str):
        cur = self
        for c in word:
            if c not in cur.sons:
                return []
            cur = cur.sons[c]
        return cur.wordIdxs

class WordFilter:
    # 思路：字典树
    def __init__(self, words: List[str]):
        self.trie1 = Trie()
        self.trie2 = Trie()
        n = len(words)
        for i in range(n):
            self.trie1.insert(words[i], i)
            self.trie2.insert(words[i][::-1], i)

    def f(self, pref: str, suff: str) -> int:
        idxs1 = self.trie1.find(pref)
        idxs2 = self.trie2.find(suff[::-1])
        # print(idxs1, idxs2)
        # idxs1和idxs2中下标有序，所以采用双指针找到最大的下标
        i, j = len(idxs1) - 1, len(idxs2) - 1
        while i >= 0:
            while j >= 0 and idxs2[j] > idxs1[i]:
                j -= 1
            if j < 0 or idxs1[i] == idxs2[j]:
                break
            i -= 1
        # print(idxs1[i])
        return idxs1[i] if i >= 0 and j >= 0 else -1

4.执行结果