Pattern visualizer

Design Add and Search Words Data Structure

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. Animated on: addWord("bad"), addWord("dad"), addWord("mad"), then search("pad"), search("bad"), search(".ad"), search("b..")..

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)step 1 / 15

•

line 5

'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

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap