This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#211) before relying on it.

Add and Search Words

An interactive visualization of the Add and Search Words data structure. Watch how a Trie supports addWord insertions and search queries with the '.' wildcard character, which matches any letter via DFS branching.

Trie LeetCode 211 ↗ Medium

The Problem

Design a data structure that supports adding new words and searching for a string where . acts as a wildcard matching any single character.

Implement the WordDictionary class:
• WordDictionary() — Initializes the data structure.
• addWord(word) — Adds word to the data structure. It can be matched later.
• search(word) — Returns true if any previously added word matches word. The character . matches any letter.

For example, after adding "bad", "dad", "mad", searching ".ad" returns true (matches all three), and searching "b.a" returns false.

Interactive Visualization

Operation

Word

Speed:

Trie Structure

Current node

Exploring (wildcard)

Match / success

Failed branch

End-of-word (#)

Operations

Step Log

Press Step or Play to begin.

Code

class WordDictionary {    val root = HashMap<Char, Any>()    fun addWord(word: String) {        var node = root        for (ch in word) {            node = node.getOrPut(ch) { HashMap<Char,Any>() } as HashMap<Char,Any>        } ; node['#'] = true    }    fun search(word: String): Boolean {        fun dfs(node: HashMap<Char,Any>, i: Int): Boolean {            if (i == word.length) {                return '#' in node }            if (word[i] == '.') {                for (child in node.keys) {                    if (child != '#' && dfs(node[child] as HashMap<Char,Any>, i + 1))                        return true                } ; return false            }            if (word[i] !in node)                return false            return dfs(node[word[i]]!! as HashMap<Char,Any>, i + 1)        }        return dfs(root, 0)    }}

class WordDictionary:    def __init__(self):        self.root = {}    def addWord(self, word):        node = self.root        for char in word:            node = node.setdefault(char, {})        node['#'] = True    def search(self, word):        def dfs(node, i):            if i == len(word):                return '#' in node            if word[i] == '.':                for child in node:                    if child != '#' and dfs(node[child], i + 1):                        return True                return False            if word[i] not in node:                return False            return dfs(node[word[i]], i + 1)        return dfs(self.root, 0)

How It Works

Key Insight

A Trie (prefix tree) stores words character by character, sharing common prefixes. Each node is a dictionary mapping characters to child nodes. An end-of-word marker ('#') signals that a complete word terminates at that node. For wildcard search, the . character triggers DFS across all children simultaneously, exploring every possible branch.

addWord

Starting from the root, traverse the trie character by character. If a character's child node doesn't exist, create it. After processing all characters, mark the final node with '#' = True to indicate a complete word. This is a standard trie insertion in O(L) time where L is the word length.

search with '.' Wildcard

The search uses DFS (depth-first search). For each character position:

Base case: If we've processed all characters (i == len(word)), check if the current node has the end-of-word marker '#'.
Wildcard '.': Try every child of the current node (except '#'). If any recursive call returns True, the search succeeds. This is where branching happens — multiple paths are explored.
Regular character: If the character exists as a child, recurse into it. Otherwise, return False.

Why Branching Matters

When searching ".ad" in a trie containing "bad", "dad", and "mad", the wildcard at position 0 causes the algorithm to explore all three branches (b, d, m) simultaneously. Each branch then continues matching "ad". All three branches succeed, so the search returns True as soon as the first successful branch is found.

Complexity

Time (addWord) O(L)

Time (search) O(26^L) worst case with all dots, O(L) without wildcards

Space O(N * L) for N words of average length L

The addWord operation is always O(L). The search operation is O(L) for exact matches, but each '.' wildcard multiplies the work by up to 26 (the number of possible child branches). In the worst case with all wildcards, this becomes O(26^L), but in practice the trie's structure prunes most branches early.