MediumA tree of characters for O(L) word and prefix lookups.
Implement a trie (prefix tree) supporting three operations: insert(word) adds a word; search(word) returns true only if the exact word was inserted; startsWith(prefix) returns true if any inserted word begins with the prefix.
Walkthrough
try:
insert(word), search(word), startsWith(prefix). Lowercase letters only. A green ring marks a word end.
A trie is a tree of characters. Every path from the root spells a prefix; a flag marks where a real word ends.
Intuition
A trie is a tree where every edge is labelled with a character, so a path from the root spells out a prefix. Words that share a prefix share the same branch — no duplication.
insert walks the word character by character, creating a child node whenever the branch does not exist yet, then flags the final node as the end of a word.
search walks the same way; if any character has no branch it fails, and at the end it checks the end-of-word flag (a prefix alone is not a match).
startsWith is search without the final flag check: reaching the end of the prefix is enough.
The algorithm
01Keep a root node whose children are keyed by character; each node has an “end of word” flag.
02insert: for each char, follow or create the child; mark the last node as a word end.
03search: for each char, fail if the child is missing; at the end return the end flag.
04startsWith: same walk, but return true as soon as the whole prefix is consumed.
Reference implementation
1
class Trie {
2
constructor() {
3
this.root = {};
4
}
5
insert(word) {
6
let node = this.root;
7
for (const c of word) {
8
if (!node[c]) node[c] = {}; // create branch if missing
9
node = node[c];
10
}
11
node.end = true; // mark end of word
12
}
13
search(word) {
14
let node = this.root;
15
for (const c of word) {
16
if (!node[c]) return false;
17
node = node[c];
18
}
19
return node.end === true;
20
}
21
startsWith(prefix) {
22
let node = this.root;
23
for (const c of prefix) {
24
if (!node[c]) return false;
25
node = node[c];
26
}
27
return true;
28
}
29
}
Complexity
Time
O(L) per operation, where L is the length of the word or prefix.