衍射的博客

记录学习中的点点滴滴

0%

前缀树（Prefix Tree）

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 4 分钟

Trie 树，又叫前缀树，字典树， 是一种有序的树形数据结构，用于高效地存储和检索字符串数据集中的键。下图是维基百科上关于trie树的一个典型例子，我们可以很清晰地看到，这棵树存储了许多前缀相似的字符串，给定一个字符串，我们可以很容易知道这个字符串是否被存储，而不需要遍历比较。

这一数据结构有相当多的应用情景，例如：

  • 自动补全：
    • 搜索提示：输入网址，跳出可能的选择
    • 输入提示：根据已经输入的字符预测可能的词组和句子
  • 拼写检查：存储合法的单词列表，快速查找是否存在合法的单词
  • 前缀匹配
  • IP路由查找

题目

leetcode 208 实现Trie（前缀树）

请你实现 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 次

分析

这道题有几个地方需要注意：

  • insert时，需要标记单词是否截止，因为trie中的节点既有可能是前缀，也有可能是单词
  • search与 startswith的区别在于， startswith只需要搜索下去，看看有没有对应的节点；而search还需要判断这个节点是否有截止信号

实现

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
class Trie(object):

    def __init__(self):
        self.root = {}

    def insert(self, word):
        """
        :type word: str
        :rtype: None
        """
        cur_node = self.root
        for c in word:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                cur_node[c]={}
                cur_node = cur_node[c]
                cur_node[0]=0 # 标记是否截止
        # 标记这个cur_node，标注上截止信号，代表这是一个词
        cur_node[0]=1

        

    def search(self, word):
        """
        :type word: str
        :rtype: bool
        """
        cur_node = self.root
        for c in word:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                return False
        # 判断有没有截止信号
        if cur_node[0]==0:
            return False
        return True
        

    def startsWith(self, prefix):
        """
        :type prefix: str
        :rtype: bool
        """
        cur_node = self.root
        for c in prefix:
            if c in cur_node.keys():
                cur_node = cur_node[c]
            else:
                return False
        return True
    
trie = Trie()
trie.insert("app")
trie.insert("apple")
trie.insert("beer")
trie.insert("add")
trie.insert("jam")
trie.insert("rental")
trie.insert("rental")
print(trie.search("apps"))
print(trie.startsWith("app"))
print(trie.search("app"))