208. Implement Trie (Prefix Tree)

  • 26.6%

https://leetcode.com/problems/implement-trie-prefix-tree/#/description

Implement a trie with insert, search, and startsWith methods.

Note:

You may assume that all inputs are consist of lowercase letters a-z.


http://blog.csdn.net/lisonglisonglisong/article/details/45584721

关于前缀树,可以参考以上文章。

一、什么是Trie树

Trie树,又叫字典树、前缀树(Prefix Tree)、单词查找树 或 键树,是一种多叉树结构。如下图:

image

上图是一棵Trie树,表示了关键字集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。从上图可以归纳出Trie树的基本性质:

  1. 根节点不包含字符,除根节点外的每一个子节点都包含一个字符。
  2. 从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符互不相同。

通常在实现的时候,会在节点结构中设置一个标志,用来标记该结点处是否构成一个单词(关键字)。

可以看出,Trie树的关键字一般都是字符串,而且Trie树把每个关键字保存在一条路径上,而不是一个结点中。另外,两个有公共前缀的关键字,在Trie树中前缀部分的路径相同,所以Trie树又叫做前缀树(Prefix Tree)。

二、Trie树的优缺点

Trie树的核心思想是空间换时间,利用字符串的公共前缀来减少无谓的字符串比较以达到提高查询效率的目的。

优点

  1. 插入和查询的效率很高,都为O(m),其中 m 是待插入/查询的字符串的长度。

-关于查询,会有人说 hash 表时间复杂度是O(1)不是更快?但是,哈希搜索的效率通常取决于 hash 函数的好坏,若一个坏的 hash 函数导致很多的冲突,效率并不一定比Trie树高。

  1. Trie树中不同的关键字不会产生冲突。

  2. Trie树只有在允许一个关键字关联多个值的情况下才有类似hash碰撞发生。

  3. Trie树不用求 hash 值,对短字符串有更快的速度。通常,求hash值也是需要遍历字符串的。

  4. Trie树可以对关键字按字典序排序。

缺点

  1. 当 hash 函数很好时,Trie树的查找效率会低于哈希搜索。

  2. 空间消耗比较大。

三、Trie树的应用

  1. 字符串检索

检索/查询功能是Trie树最原始的功能。思路就是从根节点开始一个一个字符进行比较:

如果沿路比较,发现不同的字符,则表示该字符串在集合中不存在。
如果所有的字符全部比较完并且全部相同,还需判断最后一个节点的标志位(标记该节点是否代表一个关键字)。

1
2
3
4
5
struct trie_node
{
bool isKey; // 标记该节点是否代表一个关键字
trie_node *children[26]; // 各个子节点
};
  1. 词频统计

Trie树常被搜索引擎系统用于文本词频统计 。

1
2
3
4
5
struct trie_node
{
int count; // 记录该节点代表的单词的个数
trie_node *children[26]; // 各个子节点
};

思路:为了实现词频统计,我们修改了节点结构,用一个整型变量count来计数。对每一个关键字执行插入操作,若已存在,计数加1,若不存在,插入后count置1。

注意:第一、第二种应用也都可以用 hash table 来做。

  1. 字符串排序

Trie树可以对大量字符串按字典序进行排序,思路也很简单:遍历一次所有关键字,将它们全部插入trie树,树的每个结点的所有儿子很显然地按照字母表排序,然后先序遍历输出Trie树中所有关键字即可。

  1. 前缀匹配

例如:找出一个字符串集合中所有以ab开头的字符串。我们只需要用所有字符串构造一个trie树,然后输出以a->b->开头的路径上的关键字即可。

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

  1. 作为其他数据结构和算法的辅助结构

如后缀树,AC自动机等。


https://discuss.leetcode.com/topic/13463/maybe-the-code-is-not-too-much-by-using-next-26-c

Maybe the code is not too much by using “next[26]”, 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
55
56
57
58
59
class TrieNode
{
public:
TrieNode *next[26];
bool is_word;

// Initialize your data structure here.
TrieNode(bool b = false)
{
memset(next, 0, sizeof(next));
is_word = b;
}
};

class Trie
{
TrieNode *root;
public:
Trie()
{
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string s)
{
TrieNode *p = root;
for(int i = 0; i < s.size(); ++ i)
{
if(p -> next[s[i] - 'a'] == NULL)
p -> next[s[i] - 'a'] = new TrieNode();
p = p -> next[s[i] - 'a'];
}
p -> is_word = true;
}

// Returns if the word is in the trie.
bool search(string key)
{
TrieNode *p = find(key);
return p != NULL && p -> is_word;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix)
{
return find(prefix) != NULL;
}

private:
TrieNode* find(string key)
{
TrieNode *p = root;
for(int i = 0; i < key.size() && p != NULL; ++ i)
p = p -> next[key[i] - 'a'];
return p;
}
};

https://discuss.leetcode.com/topic/13623/c-my-solution-easy-to-understand

C++, My solution, easy to understand:)

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
/**
** author: cxq
** weibo: http://weibo.com/chenxq1992
**/

class TrieNode {
public:
char content; // the character included
bool isend; // if the node is the end of a word
int shared; // the number of the node shared ,convenient to implement delete(string key), not necessary in this problem
vector<TrieNode*> children; // the children of the node
// Initialize your data structure here.
TrieNode():content(' '), isend(false), shared(0) {}
TrieNode(char ch):content(ch), isend(false), shared(0) {}
TrieNode* subNode(char ch) {
if (!children.empty()) {
for (auto child : children) {
if (child->content == ch)
return child;
}
}
return nullptr;
}
~TrieNode() {
for (auto child : children)
delete child;
}
};

class Trie {
public:
Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
void insert(string s) {
if (search(s)) return;
TrieNode* curr = root;
for (auto ch : s) {
TrieNode* child = curr->subNode(ch);
if (child != nullptr) {
curr = child;
} else {
TrieNode *newNode = new TrieNode(ch);
curr->children.push_back(newNode);
curr = newNode;
}
++curr->shared;
}
curr->isend = true;
}

// Returns if the word is in the trie.
bool search(string key) {
TrieNode* curr = root;
for (auto ch : key) {
curr = curr->subNode(ch);
if (curr == nullptr)
return false;
}
return curr->isend == true;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
bool startsWith(string prefix) {
TrieNode* curr = root;
for (auto ch : prefix) {
curr = curr->subNode(ch);
if (curr == nullptr)
return false;
}
return true;
}
~Trie() {
delete root;
}
private:
TrieNode* root;
};

https://discuss.leetcode.com/topic/14202/ac-python-solution

AC Python Solution

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
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.children = collections.defaultdict(TrieNode)
self.is_word = False

class Trie:

def __init__(self):
self.root = TrieNode()

def insert(self, word):
current = self.root
for letter in word:
current = current.children[letter]
current.is_word = True

def search(self, word):
current = self.root
for letter in word:
current = current.children.get(letter)
if current is None:
return False
return current.is_word

def startsWith(self, prefix):
current = self.root
for letter in prefix:
current = current.children.get(letter)
if current is None:
return False
return True

https://discuss.leetcode.com/topic/20375/my-python-solution

My python solution

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
class TrieNode:
# Initialize your data structure here.
def __init__(self):
self.word=False
self.children={}

class Trie:

def __init__(self):
self.root = TrieNode()

# @param {string} word
# @return {void}
# Inserts a word into the trie.
def insert(self, word):
node=self.root
for i in word:
if i not in node.children:
node.children[i]=TrieNode()
node=node.children[i]
node.word=True

# @param {string} word
# @return {boolean}
# Returns if the word is in the trie.
def search(self, word):
node=self.root
for i in word:
if i not in node.children:
return False
node=node.children[i]
return node.word

# @param {string} prefix
# @return {boolean}
# Returns if there is any word in the trie
# that starts with the given prefix.
def startsWith(self, prefix):
node=self.root
for i in prefix:
if i not in node.children:
return False
node=node.children[i]
return True


# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")

https://discuss.leetcode.com/topic/41687/compact-python-solution

Compact Python solution

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
class TrieNode(object):
def __init__(self):
self.is_word = False
self.children = collections.defaultdict(TrieNode)

class Trie(object):
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for c in word:
node = node.children[c]
node.is_word = True

def search(self, word, is_word=True):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.is_word if is_word else True

def startsWith(self, prefix):
return self.search(prefix, False)
谢谢你,可爱的朋友。