写法速查
1 | class Trie { |
745. 前缀和后缀搜索
- 字典树
- 哈希
题干
设计一个包含一些单词的特殊词典，并能够通过前缀和后缀来检索单词。
要能查找出同时满足前缀和后缀的下标最大的单词的下标
题目截图：
解法
字典树
统一记一下字典树的C++写法
1 | struct Trie { |
每个结点保存所有孩子的指针，更一般的写法应该是
unordered_map<char, Trie *> children;，每个字符对应一个结点指针weight也可以是vector类型，用来标记该结点的信息，可以是不同的类型初始化的时候要
Trie *trie;并trie = new Trie();
双字典树（一个前缀树和一个后缀树）——参考
代码：
会超时，但这个思路比较正常
-
时间复杂度可能比较高，如果天然有序的话可以手写
求交集：
set_intersection(a.begin(),a.end(),b.begin(),b.end(),inserter(result,result.begin()));
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
81struct Trie {
unordered_map<char, Trie *> children;
vector<int> weight;
};
class WordFilter
{
private:
Trie *trie1, *trie2;
public:
WordFilter(vector<string> &words)
{
trie1 = new Trie();
trie2 = new Trie();
for (int i = 0; i < words.size(); i++)
{
string word = words[i];
Trie *cur1 = trie1;
Trie *cur2 = trie2;
int m = word.size();
for (int j = 0; j < m; j++)
{
if (!cur1->children.count(word[j]))
{
cur1->children[word[j]] = new Trie();
}
cur1 = cur1->children[word[j]];
cur1->weight.push_back(i);
//
if (!cur2->children.count(word[m - j - 1]))
{
cur2->children[word[m - j - 1]] = new Trie();
}
cur2 = cur2->children[word[m - j - 1]];
cur2->weight.push_back(i);
}
}
}
int f(string pref, string suff)
{
Trie *cur1 = trie1, *cur2 = trie2;
// int m = max(pref.size(), suff.size());
int m1 = pref.size(), m2 = suff.size();
reverse(suff.begin(), suff.end());
for (int i = 0; i < m1; i++)
{
char key = pref[i];
if (!cur1->children.count(key))
{
return -1;
}
cur1 = cur1->children[key];
}
for (int i = 0; i < m2; i++)
{
char key = suff[i];
if (!cur2->children.count(key))
{
return -1;
}
cur2 = cur2->children[key];
}
vector<int> result;
// set_intersection(cur1->weight.begin(),cur1->weight.end(),cur2->weight.begin(),cur2->weight.end(),inserter(result,result.begin()));
int ans = -1;
for (int i = 0, j = 0; i < cur1->weight.size() && j < cur2->weight.size();)
{
while (i < cur1->weight.size() && j < cur2->weight.size() && cur1->weight[i] > cur2->weight[j])
j++;
while (i < cur1->weight.size() && j < cur2->weight.size() && cur1->weight[i] < cur2->weight[j])
i++;
if (i == cur1->weight.size() || j == cur2->weight.size())
return ans;
if (i < cur1->weight.size() && j < cur2->weight.size() && cur1->weight[i] == cur2->weight[j])
ans = cur1->weight[i++];
}
return ans;
}
};-
一棵树维护前缀+后缀——参考（思路清奇）
代码：
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
60struct Trie {
unordered_map<string, Trie *> children;
int weight;
};
class WordFilter {
private:
Trie *trie;
public:
WordFilter(vector<string>& words) {
trie = new Trie();
for (int i = 0; i < words.size(); i++) {
string word = words[i];
Trie *cur = trie;
int m = word.size();
for (int j = 0; j < m; j++) {
Trie *tmp = cur;
for (int k = j; k < m; k++) {
string key({word[k], '#'});
if (!tmp->children.count(key)) {
tmp->children[key] = new Trie();
}
tmp = tmp->children[key];
tmp->weight = i;
}
tmp = cur;
for (int k = j; k < m; k++) {
string key({'#', word[m - k - 1]});
if (!tmp->children.count(key)) {
tmp->children[key] = new Trie();
}
tmp = tmp->children[key];
tmp->weight = i;
}
string key({word[j], word[m - j - 1]});
if (!cur->children.count(key)) {
cur->children[key] = new Trie();
}
cur = cur->children[key];
cur->weight = i;
}
}
}
int f(string pref, string suff) {
Trie *cur = trie;
int m = max(pref.size(), suff.size());
for (int i = 0; i < m; i++) {
char c1 = i < pref.size() ? pref[i] : '#';
char c2 = i < suff.size() ? suff[suff.size() - 1 - i] : '#';
string key({c1, c2});
if (!cur->children.count(key)) {
return -1;
}
cur = cur->children[key];
}
return cur->weight;
}
};
哈希
哈希的时间甚至比上面第二种字典树还快一些
代码：
1 | class WordFilter { |