Implement Trie (Prefix Tree)
MediumTries
Build a Trie class, a tree of letters for storing words, with three methods:
insert(word) adds word. search(word) returns true if word itself was inserted, and false otherwise. startsWith(prefix) returns true if some inserted word begins with prefix.
Each test makes a new Trie and calls its methods in order. The output lists what each call returns, with null for the constructor and for insert.
Examples
Input: Trie(), insert("code"), search("code"), search("cod"), startsWith("cod"), insert("cod"), search("cod")
Output: [null, null, true, false, true, null, true]cod is only a prefix until it is inserted as a word of its own.
Input: Trie(), startsWith("a"), insert("a"), startsWith("a"), search("ab")
Output: [null, false, null, true, false]Nothing starts with a until a is inserted, and ab never is.
Constraints
1 ≤ word.length, prefix.length ≤ 2000- Words and prefixes use lowercase English letters only.
- At most 3 × 10⁴ calls in all.
Stuck?
Hint 1
Give each node a map from a letter to its child, and a flag that says whether a word ends there.
Hint 2
search and startsWith walk the same path. They differ only in whether the last node must end a word.
The idea
Store the words in a tree with a letter on each edge, so words that start the same way share one path from the root. Then search and startsWith walk the same path, and differ only in whether an inserted word must end at the last node.
Time O(L) per call, for a word of length LExtra space O(total letters inserted)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
Each node holds children, a map from a letter to the next node, and end, which says whether an inserted word stops here. The root is the empty start that every word shares.
class Trie { constructor() { this.root = { children: {}, end: false }; } insert(word) { let node = this.root; for (const letter of word) { if (!node.children[letter]) node.children[letter] = { children: {}, end: false }; node = node.children[letter]; } node.end = true; } walk(text) { let node = this.root; for (const letter of text) { const next = node.children[letter]; if (!next) return null; node = next; } return node; } search(word) { return this.walk(word)?.end === true; } startsWith(prefix) { return this.walk(prefix) !== null; }}The trap
Keeping a plain list and answering search with startsWith treats every prefix of a stored word as a stored word. Whole words and real prefix questions both come out right, so it looks finished. It fails when you search for the start of a longer word that was never inserted on its own.
class Trie { constructor() { this.words = []; } insert(word) { this.words.push(word); } search(word) { return this.words.some((w) => w.startsWith(word)); // a prefix counts as a word } startsWith(prefix) { return this.words.some((w) => w.startsWith(prefix)); }}