```
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.trie = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: void
"""
t = self.trie
for w in word:
t = t.setdefault(w,{})
t["\n"] = 0
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
t = self.trie
for w in word:
t = t.get(w)
if not t:
return False
return "\n" in t
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
t = self.trie
for w in prefix:
t = t.get(w)
if not t:
return False
return True
```