实现一个 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构成的。 - 保证所有输入均为非空字符串。
解答：
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.val = [None] * 26
self.isleaf = False
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
root = self
for i in range(len(word)):
index = (ord(word[i]) - ord('a')) % 26
if not root.val[index]:
root.val[index] = Trie()
root = root.val[index]
root.isleaf = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
root = self
for i in range(len(word)):
index = (ord(word[i]) - ord('a')) % 26
if not root.val[index]:
return False
root = root.val[index]
return root.isleaf
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
root = self
for i in range(len(prefix)):
index = (ord(prefix[i]) - ord('a')) % 26
if not root.val[index]:
return False
root = root.val[index]
return True
思路：
前缀树是做字符串匹配和子字符串搜索时很好用的一种数据结构。首先根节点为空，从根节点开始将词典中的单词依次建立前缀树，使得具有相同前缀的词在数据结构中有相同的祖先节点。举例而言，假设词典为dict=["apple", "alpha", "banana", "although"]，则前缀树为：
null
a b
p l a
p t p n
l h h a
e o a n
u a
g
h
判断一个前缀是否在词典中，只需要沿着前缀树查找，匹配整个前缀即可。判断一个词是否在词典中，也是沿着前缀树查找，如果存在一条路径且最终遍历到终止节点，则存在该词。判断终止结点不可以通过去检查当前节点是否存在子节点的方式。举例而言，对于student和students，遍历到‘t’字符时还存在子节点，但这个节点也可以被看做是student的终止节点。因此需要在建树的时候为各个节点做终止标记。
