DSA Tracker

Visualize

Design Add and Search Words Data Structure

A trie whose search can branch on a '.' wildcard

time O(L) to add; O(26^d · L) worst case to searchspace O(total characters)

This is the same trie as Implement Trie, plus one twist: a search query can contain '.', a wildcard matching any single letter. A literal character still walks one deterministic link, but a '.' forces the search to try every child at that position — branching, not walking — and stop at the first branch that leads to a match.

Details

Animated on: addWord("bad"), addWord("dad"), addWord("mad"), then search("pad"), search("bad"), search(".ad"), search("b..").

Problem:Design Add and Search Words Data StructureMedium

Pattern:Trie

A trie whose search can branch on a '.' wildcard

step 1 / 15

b
•

'b': no "b" node yet, so create it and step down.

Pseudocode
1FUNCTION addWord(word):
2  cur <- root
3  FOR ch IN word:
4    IF ch NOT IN cur.children: cur.children[ch] <- new node
5    cur <- cur.children[ch]
6  cur.end <- true
7FUNCTION search(word): RETURN dfs(root, 0)
8FUNCTION dfs(node, i):
9  IF i = LENGTH(word): RETURN node.end
10  IF word[i] != '.': RETURN (word[i] IN node.children) AND dfs(node.children[word[i]], i+1)
11  FOR child IN node.children:
12    IF dfs(child, i+1): RETURN true
13  RETURN false

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. 'b': no "b" node yet, so create it and step down.
  2. 'a': no "ba" node yet, so create it and step down.
  3. Last character 'd': create node "bad" and mark it END (double ring) — the path now spells a stored word, not just a prefix.
  4. addWord("dad"): walk/create root -> d -> da -> dad and mark "dad" END. Nodes already shared with an earlier word (like the "a" under a matching first letter) are reused, not duplicated.
  5. addWord("mad"): walk/create root -> m -> ma -> mad and mark "mad" END. Nodes already shared with an earlier word (like the "a" under a matching first letter) are reused, not duplicated.
  6. At node "root" the next character is literal 'p', and no such child exists (only b, d, m) — search("pad") returns false immediately.
  7. "bad" is literal, so walk it deterministically: "root" -> b -> ba -> bad, matching an existing chain the whole way.
  8. The query is exhausted on node "bad", whose END flag is set — search("bad") returns true.
  9. Position 0 is a wildcard: from node "root" try every child in turn — b, d, m.
  10. "ad" is literal, so walk it deterministically: "b" -> ba -> bad, matching an existing chain the whole way.
  11. The query is exhausted on node "bad", whose END flag is set — search(".ad") returns true.
  12. "b" is literal, so walk it deterministically: "root" -> b, matching an existing chain the whole way.
  13. Position 1 is a wildcard: from node "b" try every child in turn — a.
  14. Position 2 is a wildcard: from node "ba" try every child in turn — d.
  15. The query is exhausted on node "bad", whose END flag is set — search("b..") returns true.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Design Add and Search Words Data Structure in the editorAll Trie problemsBack to roadmap