DSA problem
Implement Trie (Prefix Tree)
A trie (pronounced "try"), also called a prefix tree, is a tree-shaped data structure used to efficiently store and look up strings sharing common prefixes. Unlike a hash set or a balanced BST keyed on whole words, a trie stores characters along edges so that every node represents the prefix formed by the characters from the root to that node, allowing O(L) operations where L is the word length, independent of how many words are stored.
Implement a Trie class with three public operations: insert(word) adds the word to the trie, search(word) returns true only if the exact word was previously inserted, and startsWith(prefix) returns true if any inserted word begins with the given prefix. Every input string consists only of lowercase English letters.
The classical layout uses a fixed array of 26 children per node (one slot per lowercase letter) and a boolean isEnd flag marking the last character of an inserted word. A HashMap-based variant trades a little speed for flexibility over larger alphabets. The two operations are nearly identical: walk character by character, creating nodes when missing during insertion or returning false when missing during lookup.
The distinction between search and startsWith is only the final check: search additionally requires the terminal node to have its isEnd flag set, while startsWith succeeds as soon as the walk completes. Each operation costs O(L) time and creates at most O(L) new nodes per insertion, making the trie ideal for autocomplete, dictionary lookups, and any workload where many strings share prefixes.
Examples
["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]][null,null,true,false,true,null,true]["Trie","insert","insert","search","startsWith"]
[[],["car"],["card"],["card"],["ca"]][null,null,null,true,true]["Trie","search","startsWith"]
[[],["a"],["a"]][null,false,false]Constraints
- 1 <= word.length, prefix.length <= 2000
- word and prefix consist only of lowercase English letters.
- At most 3 * 10^4 calls in total will be made to insert, search and startsWith.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.