208. Implement Trie (Prefix Tree)

Implement a trie with insert(word), search(word) (is the whole word stored?) and startsWith(prefix) (is any stored word prefixed by it?). Input is a LeetCode-style list of operations.

For lowercase words, store children in an array indexed by letter. Lookups are direct, but every node reserves 26 slots.

1class TrieNode { kids: (TrieNode | undefined)[] = new Array(26); end = false; }
2const idx = (c: string) => c.charCodeAt(0) - 97;
3class Trie {
4  root = new TrieNode();
5  insert(word: string): void {
6    let n = this.root;
7    for (const c of word) n = n.kids[idx(c)] ??= new TrieNode();
8    n.end = true;
9  }
10  private walk(s: string): TrieNode | null {
11    let n = this.root;
12    for (const c of s) { const k = n.kids[idx(c)]; if (!k) return null; n = k; }
13    return n;
14  }
15  search(word: string): boolean { return this.walk(word)?.end ?? false; }
16  startsWith(prefix: string): boolean { return this.walk(prefix) !== null; }
17}

op = Trie("")

word

empty

trie (* = end of word)

output

null

Create an empty trie.

1 / 0

Space: play/pause · ←/→: step