Problem

Implement a Trie (prefix tree) data structure that supports the following operations:

1. insert(word: str): Inserts the word into the trie.
2. search(word: str): Returns True if the word is in the trie, otherwise False.
3. starts_with(prefix: str): Returns True if there is any word in the trie that starts with the given prefix.

Examples

Example 1:

Input: trie = Trie()
trie.insert("apple")
trie.search("apple")  # returns True
trie.search("app")    # returns False
trie.starts_with("app")  # returns True

Example 2:

Input: trie = Trie()
trie.insert("bat")
trie.insert("ball")
trie.search("bat")  # returns True
trie.search("b")     # returns False
trie.starts_with("ba")  # returns True

Constraints

• 1 <= word.length <= 200
• word consists of lowercase English letters only.