Implement Trie (Prefix Tree)

Implement a trie (prefix tree) with insert, search, and startsWith. Implement Trie() and: - insert(word): Insert word into the trie. - search(word): Return true if word exists in the trie. - startsWith(prefix): Return true if any word starts with prefix. Example: Trie t; t.insert('apple'); t.search('apple')→true; t.search('app')→false; t.startsWith('app')→true; t.insert('app'); t.search('app')→true DE Shaw Tier 2 — LC 208. Structure: each node has children[26] and isEnd flag. O(m) per operation where m = word length. Talk-track: 'Tries trade space for time — O(alphabet * maxLen * numWords) space, but prefix lookups and autocomplete are O(prefix length) regardless of dictionary size.'