[LeetCode]208. 实现 Trie (前缀树)(Implement Trie (Prefix Tree))

题目描述

实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

示例:

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

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。

解题思路

前缀树的基本性质:

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

即构建一个多叉树,根结点没有值,其余每个节点有三个属性:valueis_end_wordchildren。用于存储该结点的值、是否为某个单词的结尾、孩子结点集。

代码

Python 3.6

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
class Node(object):
"""docstring for Node"""
def __init__(self, value=None, is_end_word=False):
self.value = value
self.is_end_word = is_end_word
self.children = []


class Trie:

def __init__(self):
"""
Initialize your data structure here.
"""
self.root = Node(value="<SOW>")

def add_child(self, root, value, is_end=False):
for child_node in root.children:
if child_node.value == value:
if is_end:
child_node.is_end_word = True
return child_node
cur_node = Node(value=value, is_end_word=is_end)
root.children.append(cur_node)
return cur_node

def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
cur = self.root
for idx, char in enumerate(word):
is_end = True if idx == len(word) - 1 else False
cur = self.add_child(cur, char, is_end)

def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
cur = self.root
for idx, char in enumerate(word):
for cur_child in cur.children:
if cur_child.value == char:
if idx == len(word) - 1:
return True if cur_child.is_end_word else False
else:
cur = cur_child
break
else:
return False

def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
cur = self.root
for idx, char in enumerate(prefix):
for cur_child in cur.children:
if cur_child.value == char:
if idx == len(prefix) - 1:
return True
else:
cur = cur_child
break
else:
return False