Implement Trie (Prefix Tree) in Python

A trie (pronounced "try"), or prefix tree, stores words letter by letter in a tree. Each node stands for a prefix, and each of its children adds one more letter to that prefix. Words that begin the same way share the same path from the root, so a trie can tell whether a word was added, or whether any added word starts a certain way, in time that depends only on the length of the word asked about. Autocomplete and spell checkers work this way.

Implement the class Trie:

• Trie() creates an empty trie.
• insert(word) adds the string word to the trie.
• search(word) returns True if word was inserted before, and False otherwise.
• startsWith(prefix) returns True if some inserted word starts with prefix, and False otherwise. A word counts as a prefix of itself.

The input is a list of operations, applied in order to one new trie. The output lists what the search and startsWith calls return, in order. The starter code spells these names the way your language does.

Example 1:

Input:
    insert("apple")
    search("apple")
    search("app")
    startsWith("app")
    insert("app")
    search("app")
Output: True False True True
Explanation:
"apple" was inserted, so search("apple") is True.
"app" is only the beginning of "apple": search("app") is False, but startsWith("app") is True.
After insert("app"), search("app") is True.

Example 2:

Input:
    insert("car")
    insert("cart")
    startsWith("ca")
    search("ca")
    startsWith("cat")
    search("cart")
Output: True False False True
Explanation: Both words start with "ca", but "ca" itself was never inserted. No word starts with "cat".

Example 3:

Input:
    insert("dog")
    insert("dog")
    search("dog")
    startsWith("dog")
    search("do")
    startsWith("dogs")
    search("dogs")
Output: True True False False False
Explanation: Inserting "dog" a second time changes nothing. "dog" is a prefix of itself, so startsWith("dog") is True. Nothing longer than "dog" was inserted.

Constraints:

• 1 <= word.length, prefix.length <= 30
• word and prefix consist of lowercase English letters, a to z.
• At most 105 calls in total are made to insert, search and startsWith.