Construct a trie (insert / search / startsWith)

Medium

Problem

Implement a prefix tree with insert(word), search(word) (is this exact word stored?) and startsWith(prefix) (does any stored word begin with this prefix?).

Example 1

Input:  insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output: true, false, true, true

Also asked as: Construct a trie from scratch

Test cases

Case 1

Input:    new Trie()
.insert("apple")
.search("apple")
.search("app")
.startsWith("app")
.insert("app")
.search("app")
Expected: [null,true,false,true,null,true]

Case 2

Input:    new Trie()
.insert("car")
.insert("card")
.search("car")
.search("ca")
.startsWith("card")
.startsWith("cards")
Expected: [null,null,true,false,true,false]

Case 3

Input:    new Trie()
.search("a")
.startsWith("a")
.insert("a")
.search("a")
.startsWith("a")
Expected: [false,false,null,true,true]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Nodes with a children map and an end flag

Time O(L) per opSpace O(total chars)

Each node holds a map char→child and a boolean "is a word end". Insert/search/prefix all walk character by character.

class Trie {
constructor() { this.root = { children: new Map(), end: false }; }
insert(word) {
let node = this.root;
for (const c of word) {
if (!node.children.has(c)) node.children.set(c, { children: new Map(), end: false });
node = node.children.get(c);
}
node.end = true;
}
#find(prefix) {
let node = this.root;
for (const c of prefix) {
if (!node.children.has(c)) return null;
node = node.children.get(c);
}
return node;
}
search(word) { const n = this.#find(word); return !!n && n.end; }
startsWith(prefix) { return this.#find(prefix) !== null; }
}