Implement Trie (Prefix Tree)
Implement a data structure storing lowercase words with three operations: insert(word), search(word) returning whether the exact word exists, and startsWith(prefix) returning whether any stored word begins with the prefix.
- 1 ≤ word.length ≤ 2000
- Lowercase English letters
- At most 3 · 10^4 operations
- Prefix queries
- Shared prefixes should share storage
- Lookups linear in the word length, independent of dictionary size
Prefix questions over a set of strings are answered by walking a tree keyed by characters, costing O(L) per query regardless of how many words are stored. It also lets a grid DFS abort as soon as the current path is not a prefix of any word, which is what makes multi-word search feasible.
Each node holds an array or map of child links keyed by character and an end flag. insert walks the word creating missing children and marks the last node as terminal. search walks the word and returns whether it reaches a node with end set; startsWith returns whether the walk completes at all. All three cost time proportional to the string length.
- A hash set of all prefixes supports
startsWithbut wastes O(total L^2) memory. A sorted array with binary search gives O(L log n).