Design a Trie

Design and implement a trie data structure that supports the following operations:

• insert(word: str) -> None: Inserts a word into the trie.
• search(word: str) -> bool: Returns true if a word exists in the trie, and false if not.
• has_prefix(prefix: str) -> bool: Returns true if the trie contains a word with the given prefix, and false if not.

Example:

Input: [
  insert('top'),
  insert('bye'),
  has_prefix('to'),
  search('to'),
  insert('to'),
  search('to')
]
Output: [True, False, True]

Explanation:

insert("top")    # trie has: "top"
insert("bye")    # trie has: "top" and "bye"
has_prefix("to") # prefix "to" exists in the string "top": return True
search("to")     # trie does not contain the word "to": return False
insert("to")     # trie has: "top", "bye", and "to"
search("to")     # trie contains the word "to": return True

Constraints:

• The words and prefixes consist only of lowercase English letters.

• The length of each word and prefix is at least one character.