211. Design Add and Search Words Data Structure

Design a structure that supports addWord(word) and search(word), where the search pattern may contain '.' to match any single letter. Input is a LeetCode-style list of operations.

Insert words into a trie. Searching follows one child per letter; at a '.', it tries every child and succeeds if any branch matches the rest.

1class WordDictionary {
2  root = new TrieNode();
3  addWord(word: string): void {
4    let n = this.root;
5    for (const c of word) n = n.kids.get(c) ?? n.kids.set(c, new TrieNode()).get(c)!;
6    n.end = true;
7  }
8  search(word: string, i = 0, n = this.root): boolean {
9    if (i === word.length) return n.end;
10    if (word[i] === ".")
11      return [...n.kids.values()].some((k) => this.search(word, i + 1, k));
12    const next = n.kids.get(word[i]);
13    return !!next && this.search(word, i + 1, next);
14  }
15}

op = WordDictionary()

word

empty

trie (* = end of word)

output

null

Empty trie.

1 / 0

Space: play/pause · ←/→: step