https://leetcode.com/problems/implement-trie-prefix-tree/
Implement Trie (Prefix Tree)
Total Accepted: 18703 Total Submissions: 75061 Difficulty: Medium
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Code
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.nodes = dict()
self.is_word = False
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
p = self.root
for idx, ch in enumerate(word):
if not p.nodes.get(ch, None):
p.nodes[ch] = TrieNode()
p = p.nodes[ch]
if idx==len(word)-1:
p.is_word = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
p = self.root
for idx, ch in enumerate(word):
if not p.nodes.get(ch, None):
return False
p = p.nodes[ch]
if idx==len(word)-1 and not p.is_word:
return False
return True
def startsWith(self, prefix):
"""
Returns if there is any word in the trie
that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
p = self.root
for idx, ch in enumerate(prefix):
if not p.nodes.get(ch, None):
return False
p = p.nodes[ch]
return True
# Your Trie object will be instantiated and called as such:
# trie = Trie()
# trie.insert("somestring")
# trie.search("key")
Idea
See idea about Trie:
http://www.geeksforgeeks.org/trie-insert-and-search/
https://leetcode.com/discuss/34840/maybe-the-code-is-not-too-much-by-using-next-26-c