Construct a trie (insert / search / startsWith)
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, trueAlso 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]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; }}