Implement Trie (Prefix Tree)

Implement a Trie class:

• Trie() creates an empty trie
• insert(word) stores word
• search(word) returns True if word was inserted (as a whole word)
• starts_with(prefix) returns True if some inserted word starts with prefix

Each operation should take O(length of its argument).

Tests call the methods in order; the output lists each call's return value (None for the constructor and insert).

Example 1

Input:
["Trie", "insert", "search", "search",
 "starts_with", "insert", "search"]
[[], ["apple"], ["apple"], ["app"],
 ["app"], ["app"], ["app"]]
Output:
[None, None, True, False, True, None, True]

"app" is only a prefix until it's inserted itself.

Example 2

Input:
["Trie", "insert", "insert", "starts_with",
 "starts_with", "search"]
[[], ["car"], ["cat"], ["ca"], ["co"], ["ca"]]
Output:
[None, None, None, True, False, False]

Example 3

Input:
["Trie", "search", "starts_with"]
[[], ["a"], ["a"]]
Output:
[None, False, False]

Constraints

• 1 ≤ word/prefix length ≤ 2000
• lowercase English letters only
• up to 3 · 10⁴ calls in total