首页 > 代码库 > 208. Implement Trie (Prefix Tree)
208. Implement Trie (Prefix Tree)
https://leetcode.com/problems/implement-trie-prefix-tree/#/description
Implement a trie with insert
, search
, and startsWith
methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z
.
Sol:
from collections import defaultdict class TrieNode(object): def __init__(self): self.nodes = defaultdict(TrieNode) self.isword = False class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.root for char in word: curr = curr.nodes[char] curr.isword = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.root for char in word: if char not in curr.nodes: return False curr = curr.nodes[char] return curr.isword def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ curr = self.root for char in prefix: if char not in curr.nodes: return False curr = curr.nodes[char] 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)
208. Implement Trie (Prefix Tree)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。