Implement Trie (Prefix Tree)

A trie (prefix tree) stores strings character by character so that all words sharing a prefix share a path. It powers autocomplete, spell-checkers and IP routing: checking whether any stored word starts with a prefix costs only O(len(prefix)), no matter how many words are stored.

Implement the class Trie:

• Trie() creates an empty trie.
• insert(word) stores word.
• search(word) returns True if word was previously inserted (as a whole word), else False.
• starts_with(prefix) returns True if any inserted word begins with prefix, else False.

Examples

Input:
  Trie()
  insert("apple")
  search("apple")       -> True
  search("app")         -> False   ("app" is a prefix, not a stored word)
  starts_with("app")    -> True
  insert("app")
  search("app")         -> True
Output: [None, None, True, False, True, None, True]

Constraints

• Words and prefixes consist of lowercase letters, length 1..100
• At most 1000 calls in total

Goals

• Represent a trie as nested dictionaries, one level per character
• Mark the end of a word separately from the existence of a prefix
• Share a private helper between two public methods