Implement a Trie (prefix tree) data structure that supports the following operations:
insert(word: str): Inserts the word into the trie.search(word: str): Returns True if the word is in the trie, otherwise False.starts_with(prefix: str): Returns True if there is any word in the trie that starts with the given prefix.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
1 <= word.length <= 200word consists of lowercase English letters only.