DSA · Trie · #84
Implement Trie (Prefix Tree)
Module 66 · difficulty 3/5·⏱ 30:00starts on first keystroke
A **trie** (prefix tree) is a tree data structure used to efficiently store and retrieve keys in a set of strings, supporting prefix-based lookups. Implement the `Trie` class: - `Trie()` initializes the trie object. - `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. All inputs consist of lowercase English letters `a`-`z`. The entry point is the class `Trie`.
Examples
["Trie","insert","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]→[null,null,true,false,true,null,true]— search("app") is false before "app" is inserted, but startsWith("app") is true because "apple" shares that prefix; after inserting "app", search("app") becomes true.["Trie","insert","startsWith","search"] [[],["cat"],["ca"],["ca"]]→[null,null,true,false]— "ca" is a prefix of "cat" so startsWith is true, but "ca" was never inserted as a full word so search is false.
Constraints
- · 1 <= word.length, prefix.length <= 2000
- · word and prefix consist only of lowercase English letters a-z
- · At most 3 * 10^4 calls in total will be made to insert, search, and startsWith
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.