小鲸鱼的梦境
0%

『LeetCode』745 前缀和后缀搜索

发表于 分类于 Valine：
本文字数： 6.2k 阅读时长 ≈ 6 分钟

题目

745. 前缀和后缀搜索

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

实现 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 <= 10^{4}
  • 1 <= words[i].length <= 7
  • 1 <= pref.length, suff.length <= 7
  • words[i]、pref 和 suff 仅由小写英文字母组成
  • 最多对函数 f 执行 \(10^{4}\) 次调用

标签

设计, 字典树, 字符串

相似题目

题解

【前缀和后缀搜索】字典树及其4种优化

字典树

字典树相关的内容可以看 LeetCode 的另外一题：实现 Trie (前缀树) (中等)

我们需要两个字典树，分别是前缀树和后缀树，在搜索时，记录在前缀树和后缀树中使用 dfs 找下标然后求交集，最后取最大值即可，然后，超时了🤣

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# Code language: Python
class TrieNode:
    def __init__(self):
        self.end = list()
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, s, idx):
        cur = self.root
        for c in s:
            cur = cur.next[c]
        cur.end.append(idx)
    
    def search(self, prefix):
        """ 搜索 prefix 为前缀的单词数量 """
        p = self.root
        for c in prefix:
            if c in p.next:
                p = p.next[c]
            else:
                return set()
        return self.dfs(p, set())
    
    def dfs(self, root, ans):
        """ 对字典树结点进行深度优先搜索 """
        for idx in root.end:
            ans.add(idx)
        for c, node in root.next.items():
            self.dfs(node, ans)
        return ans

class WordFilter:

    def __init__(self, words: List[str]):
        self.pref, self.suff = Trie(), Trie()
        for idx, w in enumerate(words):
            self.pref.add(w, idx)
            self.suff.add(reversed(w), idx)

    def f(self, pref: str, suff: str) -> int:
        p = self.pref.search(pref)
        s = self.suff.search(reversed(suff))
        ans = p & s
        if ans:
            return max(ans)
        return -1
  • 时间复杂度: 建立字典树 \(O(n)\), \(n\) 表示 words 的长度，搜索 \(O(m)\), \(m\) 表示字典树的大小，最坏情况下要搜索整颗字典树，相当于退化到暴力枚举求解了
  • 空间复杂度: \(O(m)\)

优化1: 观察到超时用例很多重复搜索，为搜索函数添加记忆化后可以勉强通过。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Code language: Python
class TrieNode:
    def __init__(self):
        self.end = -1
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, s, idx):
        cur = self.root
        for c in s:
            cur = cur.next[c]
        cur.end = idx
    
    def search(self, prefix):
        """ 搜索 prefix 为前缀的单词 """
        p = self.root
        for c in prefix:
            if c in p.next:
                p = p.next[c]
            else:
                return set()
        return self.dfs(p, set())
    
    def dfs(self, root, ans):
        """ 对字典树结点进行深度优先搜索 """
        if root.end != -1:
            ans.add(root.end)
        for c, node in root.next.items():
            self.dfs(node, ans)
        return ans

class WordFilter:

    def __init__(self, words: List[str]):
        self.pref, self.suff = Trie(), Trie()
        for idx, w in enumerate(words):
            self.pref.add(w, idx)
            self.suff.add(reversed(w), idx)

    @cache
    def f(self, pref: str, suff: str) -> int:
        p = self.pref.search(pref)
        s = self.suff.search(reversed(suff))
        ans = p & s
        if ans:
            return max(ans)
        return -1
  • 时间复杂度: 建立字典树 \(O(n)\), \(n\) 表示 words 的长度，搜索 \(O(m)\), \(m\) 表示字典树的大小，最坏情况下要搜索整颗字典树，相当于退化到暴力枚举求解了
  • 空间复杂度: \(O(m)\)

优化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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Code language: Python
class TrieNode:
    def __init__(self):
        self.end = -1
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, s, idx):
        cur = self.root
        for c in s:
            cur = cur.next[c]
        cur.end = idx
    
    def search(self, prefix):
        """ 搜索 prefix 为前缀的单词 """
        p = self.root
        for c in prefix:
            if c in p.next:
                p = p.next[c]
            else:
                return set()
        return self.dfs(p, set())
    
    def dfs(self, root, ans):
        """ 对字典树结点进行深度优先搜索 """
        if root.end != -1:
            ans.add(root.end)
        for c, node in root.next.items():
            self.dfs(node, ans)
        return ans

class WordFilter:

    def __init__(self, words: List[str]):
        self.words = words
        self.pref = Trie()
        for idx, w in enumerate(words):
            self.pref.add(w, idx)

    @cache
    def f(self, pref: str, suff: str) -> int:
        for idx in sorted(self.pref.search(pref), reverse=True):
            if self.words[idx].endswith(suff):
                return idx
        return -1
  • 时间复杂度: 建立字典树 \(O(n)\), \(n\) 表示 words 的长度，搜索 \(O(m)\), \(m\) 表示字典树的大小，最坏情况下要搜索整颗字典树，相当于退化到暴力枚举求解了
  • 空间复杂度: \(O(m)\)

优化3: 对搜索结果也进行记忆化，记忆化改为手动进行

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# Code language: Python
class TrieNode:
    def __init__(self):
        self.end = -1
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, s, idx):
        cur = self.root
        for c in s:
            cur = cur.next[c]
        cur.end = idx
    
    def search(self, prefix):
        """ 搜索 prefix 为前缀的单词 """
        p = self.root
        for c in prefix:
            if c in p.next:
                p = p.next[c]
            else:
                return set()
        return self.dfs(p, set())
    
    def dfs(self, root, ans):
        """ 对字典树结点进行深度优先搜索 """
        if root.end != -1:
            ans.add(root.end)
        for c, node in root.next.items():
            self.dfs(node, ans)
        return ans

class WordFilter:

    def __init__(self, words: List[str]):
        self.words = words
        self.pref = Trie()
        for idx, w in enumerate(words):
            self.pref.add(w, idx)
        self.pref_cache = dict()
        self.pref_suff = dict()

    def f(self, pref: str, suff: str) -> int:
        key = f"{pref}_{suff}"
        if key in self.pref_suff:
            return self.pref_suff[key]
        if pref not in self.pref_cache:
            self.pref_cache[pref] = sorted(self.pref.search(pref), reverse=True)
        ans = self.pref_cache[pref]
        for idx in ans:
            if self.words[idx].endswith(suff):
                self.pref_suff[key] = idx
                return idx
        self.pref_suff[key] = -1
        return -1
  • 时间复杂度: 建立字典树 \(O(n)\), \(n\) 表示 words 的长度，搜索 \(O(m)\), \(m\) 表示字典树的大小，最坏情况下要搜索整颗字典树，相当于退化到暴力枚举求解了
  • 空间复杂度: \(O(m)\)

优化4：参考了三叶姐的思路，直接在字典树中记录经过的结点，略去了最大的 dfs 开销，此时搜索的记忆化也可以省去了

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Code language: Python
class TrieNode:
    def __init__(self):
        self.string = list()
        self.next = defaultdict(TrieNode)

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def add(self, s, idx):
        cur = self.root
        for c in s:
            cur = cur.next[c]
            cur.string.append(idx)
    
    def search(self, prefix):
        """ 搜索 prefix 为前缀的单词 """
        p = self.root
        for c in prefix:
            if c in p.next:
                p = p.next[c]
            else:
                return []
        return p.string

class WordFilter:

    def __init__(self, words: List[str]):
        self.words = words
        self.pref = Trie()
        for idx, w in enumerate(words):
            self.pref.add(w, idx)
        self.pref_suff = dict()

    def f(self, pref: str, suff: str) -> int:
        key = f"{pref}_{suff}"
        if key in self.pref_suff:
            return self.pref_suff[key]
        for idx in reversed(self.pref.search(pref)):
            if self.words[idx].endswith(suff):
                self.pref_suff[key] = idx
                return idx
        self.pref_suff[key] = -1
        return -1
  • 时间复杂度: 建立字典树 \(O(n)\), \(n\) 表示 words 的长度，搜索 \(O(m)\), \(m \leq 7\) 表示字典树的深度
  • 空间复杂度: \(O(m)\)

最后放一个本题的优化提交记录~

1657766506020

如果对你有帮助的话，请给我点个赞吧~

欢迎前往 我的博客 或 Algorithm - Github 查看更多题解

--- ♥ end ♥ ---

欢迎关注我呀~