Implement a Prefix Search (Trie)

Problem Design a dictionary that supports inserting words and testing whether any stored word starts with a given prefix — the core of an autocomplete lookup.

Input / Output

• Input: a sequence of operations — insert(word) and startsWith(prefix).
• Output: startsWith(prefix) returns true if at least one inserted word has prefix as a prefix, else false.

Constraints

• Up to 10^5 words; lowercase English letters.
• startsWith should run in time proportional to the prefix length, independent of how many words are stored.

Example

• insert("car"); startsWith("ca") → true; startsWith("cb") → false.
• Distinguishing "is a stored word" from "is a prefix of some word" is a separate check worth clarifying.