友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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]、pref和suff仅由小写英文字母组成 -
最多对函数
f执行104次调用
思路分析
前缀树。对单词正反存在两棵前缀树上。查找时，使用前后缀分别查找即可。
-
一刷
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-06-05 21:59:46
*/
class WordFilter {
private Trie head;
private Trie tail;
private String[] words;
public WordFilter(String[] words) {
head = new Trie();
tail = new Trie();
this.words = words;
for (int i = 0; i < words.length; i++) {
char[] chars = words[i].toCharArray();
add(head, chars, i, false);
add(tail, chars, i, true);
}
}
public int f(String pref, String suff) {
Set<Integer> i1 = search(head, pref.toCharArray(), false);
if (i1.isEmpty()) {
return -1;
}
Set<Integer> i2 = search(tail, suff.toCharArray(), true);
if (i2.isEmpty()) {
return -1;
}
int result = -1;
for (Integer i : i1) {
if (!i2.contains(i)) {
continue;
}
result = Math.max(result, i);
}
return result;
}
private void add(Trie trie, char[] word, int index, boolean reverse) {
for (int i = 0; i < word.length; i++) {
char c = word[reverse ? word.length - 1 - i : i];
int idx = c - 'a';
if (trie.children[idx] == null) {
trie.children[idx] = new Trie();
}
trie = trie.children[idx];
if (i == word.length - 1) {
trie.index = Math.max(trie.index, index);
}
}
}
private Set<Integer> search(Trie trie, char[] word, boolean reverse) {
for (int i = 0; i < word.length; i++) {
int idx = word[reverse ? word.length - 1 - i : i] - 'a';
if (trie.children[idx] == null) {
return Collections.emptySet();
}
trie = trie.children[idx];
}
Set<Integer> result = new HashSet<>();
Queue<Trie> queue = new LinkedList<>(List.of(trie));
while (!queue.isEmpty()) {
Trie node = queue.poll();
if (node.index >= 0) {
result.add(node.index);
}
for (Trie child : node.children) {
if (Objects.isNull(child)) {
continue;
}
queue.offer(child);
}
}
return result;
}
private static class Trie {
private final Trie[] children = new Trie[26];
// 这个地方可以优化一下，在每一层都加入坐标，
// 这样就不需要深度遍历到叶子节点。
private int index = -1;
}
}