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

Examples

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