Implement Trie (Prefix Tree)

Build a prefix tree over lowercase words.

• Trie() creates an empty trie.
• insert(word) adds word (inserting the same word twice is harmless).
• search(word) returns True only if word itself was inserted.
• starts_with(prefix) returns True if some inserted word begins with prefix.

Every operation should cost O(length of the argument), independent of how many words are stored.

t = Trie()
t.insert("card")
t.search("car")       # False (only a prefix)
t.starts_with("car")  # True
t.insert("car")
t.search("car")       # True
t.starts_with("cat")  # False

Constraints: words and prefixes have length 1..2000 and use a-z; the tests store tens of thousands of words.