leetcode hot100 tire前缀树
208. 实现 Trie (前缀树)
已解答
中等
相关标签
相关企业
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
class TreeNode(object):
def __init__(self):
self.isword=False
self.alpha_dict={}
class Trie(object):
def __init__(self):
self.root = TreeNode()
def insert(self, word):
"""
:type word: str
:rtype: None
"""
tmp = self.root
for substr in word:
if tmp.alpha_dict.get(substr):
tmp = tmp.alpha_dict.get(substr)
continue
else:
# 插入这个值
tmp.alpha_dict[substr]=TreeNode()
tmp = tmp.alpha_dict[substr]
tmp.isword=True
def search(self, word):
"""
:type word: str
:rtype: bool
"""
tmp = self.root
for substr in word:
if tmp.alpha_dict.get(substr):
tmp = tmp.alpha_dict.get(substr)
continue
else:
# 插入这个值
return False
return tmp.isword
def startsWith(self, prefix):
"""
:type prefix: str
:rtype: bool
"""
tmp = self.root
for substr in prefix:
if tmp.alpha_dict.get(substr):
tmp = tmp.alpha_dict.get(substr)
continue
else:
# 插入这个值
return False
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
使用前缀树来做，就是直接的把一个treenode变为next是一个alpha dict就行了
在保存一个bool值判断到这里是不是一个词语