Coding interview problems › Design & Tries

🗃️ Design & Tries Medium

Design Add and Search Words (Wildcard Trie)

Design Add and Search Words explained: a trie where '.' matches any letter, searched with DFS over children, tested Python, complexity and a live trie visual.

Also searched as: add and search word data structure · trie with wildcard dot search · word dictionary with regex dot

🌲

Try it live Free

Trie & Autocomplete

Watch words branch into the trie and prefixes get reused; a wildcard search follows every branch at a dot instead of a single one.

Also useful: Backtracking: Subsets, Permutations & Pruning

Open the playground →

The problem

Design a word dictionary with add_word(word) and search(pattern). The pattern contains lowercase letters and the wildcard ., which matches any single letter. search returns whether any added word matches the whole pattern.

Inputadd_word("bad"), add_word("dad"), add_word("mad"); search("pad"), search("bad"), search(".ad"), search("b..")
OutputFalse, True, True, True

The key insight

Store words in a trie. A normal letter follows one child, as usual. A . could be any letter, so you branch into every child and succeed if any branch matches the rest of the pattern. That is a depth-first search over the trie, guided by the pattern.

Brute force first: Storing words in a list and comparing each one with the pattern costs O(number of words × L) per search.

Step-by-step approach

  1. Use the same TrieNode as a normal trie: a children map and an end flag.
  2. add_word is a normal trie insert.
  3. search calls dfs(node, i): if i equals the pattern length, return node.end.
  4. If pattern[i] is a letter, move to that child (fail if missing) and recurse with i + 1.
  5. If it is ., try dfs(child, i + 1) for every child and return true if any succeeds.

Python solution

PYTHON 3tested
class TrieNode:
    __slots__ = ("children", "end")

    def __init__(self):
        self.children = {}
        self.end = False


class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def add_word(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.end = True

    def search(self, pattern):
        def dfs(node, i):
            if i == len(pattern):
                return node.end
            ch = pattern[i]
            if ch == ".":                      # wildcard: try every child
                return any(dfs(child, i + 1) for child in node.children.values())
            nxt = node.children.get(ch)
            return nxt is not None and dfs(nxt, i + 1)

        return dfs(self.root, 0)

Complexity

Timeadd O(L); search O(L) to O(26^L)
SpaceO(total characters)

A pattern without dots is an O(L) walk. Each dot can branch into up to 26 children, so a pattern of all dots may explore much of the trie, bounded by the number of nodes at that depth.

Common mistakes

Frequently asked questions

What is the time and space complexity of the wildcard trie?

add_word is O(L). search is O(L) without wildcards and, in the worst case with many dots, can visit every trie node at those depths, up to O(26^L). Space is O(total characters stored).

Can I speed up searches with many dots?

Group words by length first so a pattern only searches words of its own length, or keep a separate trie per length. Both prune large parts of the search.

Why not use regular expressions?

A regex scan over every stored word costs O(number of words × L) per query. The trie shares prefixes, so most queries touch far fewer characters.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Design & Tries LRU Cache (HashMap + Linked List) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.