0745：前缀和后缀搜索（★★）

2017-01-14 约 543 字预计阅读 2 分钟次阅读

力扣第 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 <= 10⁴
1 <= words[i].length <= 7
1 <= pref.length, suff.length <= 7
words[i]、pref 和 suff 仅由小写英文字母组成
最多对函数 f 执行 10⁴ 次调用

分析

#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

目录

0745：前缀和后缀搜索（★★）

题目

分析

#1 打表

#2 字典树

解答