【每日一题】面试高频考点 - LeetCode 208.实现Trie(前缀树)

本文最后更新于:2021年4月14日 下午

LeetCode 208. 实现Trie(前缀树)

思路

这是一道Trie树的标程题,按照Trie树的构建标准写即可,引用Wiki的一段

计算机科学中,trie,又称前缀树字典树,是一种有序,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie这个术语来自于retrieval。根据词源学,trie的发明者Edward Fredkin把它读作/ˈtriː/ “tree”。[1][2]但是,其他作者把它读作/ˈtraɪ/ “try”。[1][2][3]

在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。

键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示trie的原理。

trie中的键通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串比特,可以用于表示整数或者内存地址。

Trie树的应用

trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。[4]

C++代码

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
class Trie {
public:
int son[100010][26], ok[100010];
int idx;
/** Initialize your data structure here. */
Trie() {
memset(son, 0 ,sizeof(son));
memset(ok,0,sizeof(ok));
}

/** Inserts a word into the trie. */
void insert(string word) {
int p=0;
for(auto c:word)
{
int u=c-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
ok[p]=1;
}

/** Returns if the word is in the trie. */
bool search(string word) {
int p=0;
for(auto c:word)
{
int u=c-'a';
if(!son[p][u]) return false;
p=son[p][u];
}
return ok[p];
}

/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
int p=0;
for(auto c:prefix)
{
int u=c-'a';
if(!son[p][u]) return false;
p=son[p][u];
}
return true;
}
};

/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/

AcWing 142.前缀统计

思路

Trie树的变种应用

C++代码

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
#include<iostream>


using namespace std;
const int N=1000010;

int n,m;
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
int p=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) son[p][u]=++idx;
p=son[p][u];
}
cnt[p]++;
}

int query(char *str)
{
int p=0, res=0;
for(int i=0;str[i];i++)
{
int u=str[i]-'a';
if(!son[p][u]) break;
p=son[p][u];
res+=cnt[p];
}
return res;
}

int main()
{
cin>>n>>m;
while(n--)
{
cin>>str;
insert(str);
}
while(m--)
{
cin>>str;
cout<<query(str)<<endl;
}
return 0;
}