208.实现Trie(前缀树)
Trie树(又叫「前缀树」或「字典树」)是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。
其核心是使用「边」来代表有无字符,使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

一、二维数组(不易理解)
使用二维数组
trie[]
来存储所有的单词字符。使用
index
来自增记录到底用了多少个格子(相当于给被用到格子进行编号)。使用
count
数组记录某个格子被「被标记为结尾的次数」(当idx
编号的格子被标记了n
次,则有count[idx]=n
)。如插入”apple“、”ape“后,trie数组、count数组如下:
abcde...l...p...zcount[i]0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
2
0
0
2
0
0
0
0
6
0
3
0
0
3
0
0
0
0
0
4
0
0
0
4
0
0
0
0
5
0
0
0
0
5
0
0
0
0
0
0
0
0
1
6
0
0
0
0
0
0
0
0
1
class Trie:
def __init__(self):
self.N = 100000
# 存储所有字符
self.trie = [[0] * 26 for _ in range(self.N)]
self.count = [0] * self.N
self.index = 0
# 实现插入
def insert(self, word: str) -> None:
# 横轴表示格子,纵轴表示字符
# trie[i][j]表示要匹配的下一个格子序号
i = 0 # 格子从0开始
for s in word:
j = ord(s) - ord('a')
# 格子为0表示没匹配过
if self.trie[i][j] == 0:
# 使用的格子数+1
self.index += 1
self.trie[i][j] = self.index
i = self.trie[i][j]
# 统计i处的格子作为结尾的个数
self.count[i] += 1
# 实现搜索
def search(self, word: str) -> bool:
i = 0
for s in word:
j = ord(s) - ord('a')
# 格子为0表示没匹配过
if self.trie[i][j] == 0:
return False
# 否则匹配下一位
i = self.trie[i][j]
# 最后看i处格子被作为结尾的次数,只要不是0,都说明该字符串存在
return self.count[i] != 0
# 查找字典中是否有以prefix为前缀的字符串
def startsWith(self, prefix: str) -> bool:
i = 0
for s in prefix:
j = ord(s) - ord('a')
# 格子为0表示没匹配过
if self.trie[i][j] == 0:
return False
# 否则匹配下一位
i = self.trie[i][j]
# 与search函数的区别是,没有False,就是True
return True
二、TrieNode(推荐)
定义数据结构TrieNode,是一个26叉树
# 数据结构,Trie树节点,表示一个字符
class TrieNode:
def __init__(self):
self.end = False # 标志该字符是否为某个单词的结尾
self.tns = [None] * 26 #记录该字符的后续字符,26个分支表示a-z,None表示无后续
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
i = self.root
for s in word:
j = ord(s) - ord('a')
if i.tns[j] == None:
i.tns[j] = TrieNode()
i = i.tns[j]
i.end = True
def search(self, word: str) -> bool:
i = self.root
for s in word:
j = ord(s) - ord('a')
if i.tns[j] == None:
return False
i = i.tns[j]
return i.end
def startsWith(self, prefix: str) -> bool:
i = self.root
for s in prefix:
j = ord(s) - ord('a')
if i.tns[j] == None:
return False
i = i.tns[j]
return True
最后更新于