Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.
My code:
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.store_dict={}
self.start_dict={}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
self.store_dict[word]=1
for i in range(1,len(word)+1):
self.start_dict[word[:i]]=1
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
if word in self.store_dict.keys():
return True
return False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
if prefix in self.start_dict.keys():
return True
return False
# 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)
Solution: https://leetcode.com/problems/implement-trie-prefix-tree/