Trie前缀树

发表于 | 更新于: | 分类于 ， |
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

cover

一、题干：

208. 实现 Trie (前缀树)

**Trie**（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

  • Trie() 初始化前缀树对象。
  • void insert(String word) 向前缀树中插入字符串 word 。
  • boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
  • boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

  • 1 <= word.length, prefix.length <= 2000
  • word 和 prefix 仅由小写英文字母组成
  • insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

二、关于前缀树：

前缀树又被称为字典树，是一种树状数据结构，可以存储字符串集合，尤其对于相同前缀的字符串非常友好

这一高效的数据结构有多种应用：

1
2
3
4
1.自动补全
2.拼写检查
3.IP 路由 (最长前缀匹配)
4.打字预测

存储方式：

tree

根节点上存储的全都是某几个字符串的公共字符，因此便于查找前缀。每一个节点里都是一个字符元素。在与哈希表相似的原理支持下，按字符搜索可以将其复杂度降低至O（n）（这里n是字符串长度）平衡二叉树复杂度为O（logn），可见在字符串的长度较小时前缀树更为合适。

实现：

具体实现方式其实有两种——1、用数组实现和2、用Hash Map实现。

数组解法基本思路是每个节点用一个长度26的数组储存该节点字符情况，并用一个bool数值判断是否到达末尾（即后续无字符节点）。

代码（数组）：

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
typedef struct {
  struct Trie* wd[26];
  bool end;//判断是否为单词结尾的bool值
} Trie;
/** Initialize your data structure here. */
Trie* trieCreate() {
  Trie* p=(Trie*)malloc(sizeof(Trie));
  for(int i=0;i<26;i++){
​    p->wd[i]=NULL;
  }
  p->end=false;
  return p;
}
/** Inserts a word into the trie. */
void trieInsert(Trie* obj, char * word) {
 for(int i=0;i<strlen(word);i++){
   if(obj->wd[word[i]-97]==NULL){
​     Trie* p=trieCreate();
​     obj->wd[word[i]-97]=p;//利用关键字进行匹配比对
   }
   obj=obj->wd[word[i]-97];
 }
 obj->end=true;
}
/** Returns if the word is in the trie. */
bool trieSearch(Trie* obj, char * word) {
  for(int i=0;i<strlen(word);i++){
   if(obj->wd[word[i]-97]!=NULL){
​     obj=obj->wd[word[i]-97];
   }
   else{
​     return false;//返回的是最后匹配节点的bool值
   }
 }
 return obj->end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool trieStartsWith(Trie* obj, char * prefix) {
  for(int i=0;i<strlen(prefix);i++){
   if(obj->wd[prefix[i]-97]!=NULL){
​     obj=obj->wd[prefix[i]-97];
   }
   else{
​     return false;
   }
 }
 return true;
}
void trieFree(Trie* obj) {
  free(obj);
}
/**
 \* Your Trie struct will be instantiated and called as such:
 \* Trie* obj = trieCreate();
 \* trieInsert(obj, word);
 \* bool param_2 = trieSearch(obj, word);
 \* bool param_3 = trieStartsWith(obj, prefix);
 \* trieFree(obj);
*/

搜索字符串和前缀的方式相近，都是随节点向下匹配，只不过字符串要考虑当前是否为末尾（bool值判定）

Hash Map方法：

思路：

上面的方法预先对每个节点设置了一个长为26的数组，浪费空间。我们可以使用字典来实现。

对于每个节点都是一个字典dict， 它的键为后续的字符，值为这个字符对应的字典，同时对单词结尾的字符，我们添加一个键-1，如果-1在这个字典中，说明这个单词存在。整个结构相当于一层一层嵌套的字典，所以叫字典树。

参考资料：

Trie 前缀树原理及两种实现

数据结构之字典

字典树（前缀树）的实现