题目链接#

LeetCode 208. 实现 Trie（前缀树）

题目描述#

请你实现 Trie 类，支持以下操作：

• insert(word)：向前缀树中插入字符串 word
• search(word)：如果字符串 word 在前缀树中，返回 true
• startsWith(prefix)：如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true

解题思路：设计 TrieNode 节点#

Trie 本质上是一棵专门存字符串的树。

和普通二叉树不同，它不是每个节点只连左右两个孩子， 而是：

每个节点都可以根据不同字符，连向不同的子节点。

所以一个节点最少需要维护两样东西：

1
self.children = {}

1
{
2
    'a': TrieNode(),
3
    'b': TrieNode(),
4
    'c': TrieNode()
5
}

1
class TrieNode:
2
    def __init__(self):
3
        self.children = {}
4
        self.is_end = False

Trie 类整体实现#

有了节点之后，Trie 本体就简单了。

我们只需要维护一个根节点 root，后续所有操作都从根开始往下走。

1
class TrieNode:
2
    def __init__(self):
3
        self.children = {}
4
        self.is_end = False
5

6

7
class Trie:
8

9
    def __init__(self):
10
        self.root = TrieNode()
11

12
    def insert(self, word: str) -> None:
13
        cur = self.root
14
        for ch in word:
15
            if ch not in cur.children:
16
                cur.children[ch] = TrieNode()
17
            cur = cur.children[ch]
18
        cur.is_end = True
19

20
    def search(self, word: str) -> bool:
21
        cur = self.root
22
        for ch in word:
23
            if ch not in cur.children:
24
                return False
25
            cur = cur.children[ch]
26
        return cur.is_end
27

28
    def startsWith(self, prefix: str) -> bool:
29
        cur = self.root
30
        for ch in prefix:
31
            if ch not in cur.children:
32
                return False
33
            cur = cur.children[ch]
34
        return True

下面把三个操作拆开说。

1. 插入操作 insert(word)#

插入一个单词时，我们从根节点出发，逐个处理字符。

如果当前字符对应的子节点不存在，就创建； 如果已经存在，就沿着已有路径继续往下走。

最后走到单词末尾时，把当前节点标记成单词结尾：

1
cur.is_end = True

1
root
2
 └── a
3
      └── p
4
           └── p
5
                └── l
6
                     └── e

2. 查找完整单词 search(word)#

查找时也是从根节点开始，逐个字符往下找。

1
return cur.is_end

1
apple

3. 判断前缀 startsWith(prefix)#

这一步和 search 非常像， 区别只在最后一句。

对于前缀判断来说，只要这条路径存在，就够了。

也就是说：

• 只要每个字符都能往下找到
• 就说明存在某个单词以这个前缀开头

因此不用再判断 is_end，直接返回 True。

search 和 startsWith 的区别#

这题最值得记住的，其实就是这对兄弟的区别。

可以粗暴记成：

search 要验明正身，startsWith 只看你是不是路过。

复杂度分析#

设字符串长度为 n。

这题的关键点#

虽然代码不长，但有两个地方最容易写偏：

小结#

这道题是标准 Trie 入门题，重点不在花活，而在把结构搭稳。

整个实现抓住三件事就行：

• 节点里要有 children
• 节点里要有 is_end
• search 和 startsWith 的判断标准不一样

如果只记一句话，那就是：

Trie 按字符存路径，search 看结尾，startsWith 看路径。

模板题别嫌简单，简单题写扎实，后面遇到单词搜索、前缀统计、字典树剪枝，才不会一脸懵。

继续刷，树还很多，路也还长，但这棵前缀树，今天算是栽稳了。🦐