Implement Trie (Prefix Tree)
Problem: Implement Trie (Prefix Tree)
A trie can be used to manage words. We can use a list to manage children at a TrieNode and use a boolean value to mark whether the current node represents for a word.
class TrieNode(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.isWord = False
self.children = [None] * 26
class Trie(object):
def __init__(self):
self.root = TrieNode()
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
cur = self.root
for c in word:
if cur.children[ord(c)-ord('a')] == None:
cur.children[ord(c)-ord('a')] = TrieNode()
cur = cur.children[ord(c)-ord('a')]
cur.isWord = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
cur = self.root
for c in word:
if cur.children[ord(c)-ord('a')] == None:
return False
cur = cur.children[ord(c)-ord('a')]
return cur.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
"""
cur = self.root
for c in prefix:
if cur.children[ord(c)-ord('a')] == None:
return False
cur = cur.children[ord(c)-ord('a')]
return True