# using python

# To implement tree like structure, first need to implement node class
class TrieNode:
    def __init__(self):
    	"""
    	1. A boolean attribute indicating if this is the end of word
    	"""
        self.isWord = False

        """
        2. A dictionary to record the child nodes
        """
        # To avoid key error using empty dict(), we use collections.defaultdict() instead. If the passing item is not found, instead of throwing error, it will just create a new entry
        self.child = collections.defaultdict(TrieNode)
        # In python we don't need to explicitly declare constructor
        
class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        
    
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        # 1. iterate top-down and append 
        curr = self.root
        for w in word:
            curr = curr.child[w]
        # 2. check is end of word
        curr.isWord = True

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        # 1. iterate top-down and append 
        curr = self.root
        for w in word:
            if w not in curr.child:
                return False
            else:
                curr = curr.child[w]
        # 2. check is end of word
        return curr.isWord
        

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        # 1. iterate top-down and append 
        curr = self.root
        for p in prefix:
            if p not in curr.child:
                return False
            else:
                curr = curr.child[p]
        # 2. Warning: 'word' is prefix of 'word' itself, no need to check isWord
        return True