1. 题目来源
- 分类:字典树
- Leetcode208:Trie树的基本操作
2. 题目描述
实现一个 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 构成的。保证所有输入均为非空字符串。
3. 解题思路
根据Trie Tree(字典树/前缀树/单词查找树)对Trie基本结构,查找,插入等性质的描述进行编写。
4. 编程实现
Python
# 构建字典树结点
class TrieNode:
def __init__(self):
# isEnd是否为单词结尾
self.isEnd = False
# children
self.next = [None for i in range(26)]
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
node = self.root
for i in range(len(word)):
#本题目为0-25长度数组是否为None
if node.next[ord(word[i]) - ord('a')] == None:
node.next[ord(word[i]) - ord('a')] = TrieNode()
node = node.next[ord(word[i]) - ord('a')]
node.isEnd = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
node = self.root
for i in range(len(word)):
if node.next[ord(word[i]) - ord('a')] == None:
return False
node = node.next[ord(word[i]) - ord('a')]
# 确认为单词结束还是只是某个单词前缀
return node.isEnd
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
node = self.root
for i in range(len(prefix)):
if node.next[ord(prefix[i]) - ord('a')] == None:
return False
node = node.next[ord(prefix[i]) - ord('a')]
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)
网友评论