目录

0745:前缀和后缀搜索(★★)

力扣第 745 题

题目

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

实现 WordFilter 类:

  • WordFilter(string[] words) 使用词典中的单词 words 初始化对象。
  • f(string pref, string suff) 返回词典中具有前缀 pref 和后缀 suff 的单词的下标。如果存在不止一个满足要求的下标,返回其中 最大的下标 。如果不存在这样的单词,返回 -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 <= 104
  • 1 <= words[i].length <= 7
  • 1 <= pref.length, suff.length <= 7
  • words[i]prefsuff 仅由小写英文字母组成
  • 最多对函数 f 执行 104 次调用

相似问题:

分析

#1 打表

可以先将所有可能的 <前缀、后缀> 组合都计算出结果,查询时直接返回即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class WordFilter:

    def __init__(self, words: List[str]):
        self.d = defaultdict(lambda:-1)
        for i,w in enumerate(words):
            for j in range(1,len(w)+1):
                for k in range(len(w)):
                    key = (w[:j],w[k:])
                    self.d[key] = max(self.d[key],i)

    def f(self, pref: str, suff: str) -> int:
        return self.d[(pref,suff)]

2008 ms

#2 字典树

也可以用前缀、后缀字典树分别保存单词的下标集合。

查询时,先找到前缀、后缀对应的下标集合,再找交集中最大的下标。

为了加速查找交集的最大下标,可以用状态压缩代替集合。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class WordFilter:

    def __init__(self, words: List[str]):
        T = lambda: defaultdict(T)
        self.t1, self.t2 = T(), T()
        for i,w in enumerate(words):
            p = self.t1
            for c in w:
                p = p[c]
                p['#'] = p.get('#',0)|1<<i
            p = self.t2
            for c in w[::-1]:
                p = p[c]
                p['#'] = p.get('#',0)|1<<i

    def f(self, pref: str, suff: str) -> int:
        p = self.t1
        for c in pref:
            if c not in p:
                return -1
            p = p[c]
        a = p['#']
        p = self.t2
        for c in suff[::-1]:
            if c not in p:
                return -1
            p = p[c]
        b = p['#']
        return (a&b).bit_length()-1

1000 ms