83. Implement Trie - Autocomplete/Search

You're building an autocomplete feature for a search bar. As users type, you need to quickly find all words that start with the typed prefix. A Trie (Prefix Tree) is the perfect data structure for this use case.

Implement a Trie (prefix tree) with the following operations:

• insert(word): Inserts the string word into the trie
• search(word): Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise
• startsWith(prefix): Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise

Requirements

1. Basic Operations

• Insert words into the trie
• Search for complete words
• Check if prefix exists
• Handle empty strings

Example Usage

const trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true
trie.search("app");     // false
trie.startsWith("app"); // true
trie.insert("app");
trie.search("app");     // true

Real-World Context

This problem models real search and autocomplete features:

• Search autocomplete: Find suggestions as user types
• Spell checker: Check if words exist in dictionary
• Prefix matching: Find all words with given prefix
• Search engines: Efficient prefix-based search