text: # https://leetcode.com/problems/implement-trie-prefix-tree/
  
  
  class TrieNode:
      def __init__(self):
          self.children = {}
          self.end = False
  
  
  class Trie:
      def __init__(self):
          """
          Initialize your data structure here.
          """
          self.root = TrieNode()
  
      def insert(self, word):
          """
          Inserts a word into the trie.
          :type word: str
          :rtype: void
          """
          root = self.root
          for c in word:
              if c not in root.children:
                  root.children[c] = TrieNode()
              root = root.children[c]
          root.end = True
  
      def search(self, word):
          """
          Returns if the word is in the trie.
          :type word: str
          :rtype: bool
          """
          root = self.root
          for c in word:
              if c not in root.children:
                  return False
              root = root.children[c]
          return root.end
  
      def startsWith(self, prefix):
          """
          Returns if there is any word in the trie that starts with the given prefix.
          :type prefix: str
          :rtype: bool
          """
          root = self.root
          for c in prefix:
              if c not in root.children:
                  return False
              root = root.children[c]
          return True
  
  
  # 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)
  