# Trie data strucuture

class Node:

def __init__(self, val):
self.val = val
self.children = [None] * 26
self.end = False

class Trie:

def __init__(self):
self.root = Node("Trie")

def insert(self, word: str) -> None:
temp = self.root
for w in word:
if (temp.children[ord(w)-97] != None):
temp = temp.children[ord(w)-97]
else:
newNode = Node(w)
temp.children[ord(w)-97] = newNode
temp = newNode
temp.end = True

def search(self, word: str) -> bool:
temp = self.root
for w in word:
if (temp.children[ord(w)-97] != None):
temp = temp.children[ord(w)-97]
else:
return False
if (temp.end):
return True
return False

def startsWith(self, prefix: str) -> bool:
temp = self.root
for w in prefix:
if (temp.children[ord(w)-97] != None):
temp = temp.children[ord(w)-97]
else:
return False

return True