Course contentsShow
← Computer Science
Lesson 629 of 2,87215. Tries and Specialized TreesFree lesson

Wildcard Matching in Tries

Extending trie search to handle wildcard characters by exploring multiple paths during traversal.

Wildcard Matching in Tries

What you'll learn: How to extend trie searches to handle wildcard characters (like * or .) by exploring multiple branches simultaneously.

The Core Idea

In regular trie search, you follow a single path through the tree based on each character in your query. But what if your search contains a wildcard that can match any character? For example, searching for "c.t" should match "cat", "cot", and "cut".

The solution is elegant: when you encounter a wildcard character during traversal, explore all possible child branches instead of just one. This means your search becomes recursive, checking multiple paths through the trie in parallel.

How It Works

Imagine searching for "b.g" in a trie containing "bag", "big", and "bug":

  1. Start at root, process 'b' → follow the single 'b' branch
  2. Encounter wildcard '.' → branch out: check all children ('a', 'i', 'u')
  3. From each branch, continue with 'g' → verify which paths have 'g'
  4. Collect all valid words that complete the pattern

This is different from regular search because:

  • Regular search: one character → one path
  • Wildcard search: one wildcard → all paths at that level

You typically implement this with recursion: for each wildcard position, recursively search all available child nodes and combine the results.

Performance Consideration

Wildcards increase search complexity. If your trie has k children per node on average and you have w wildcards in a word of length n, worst-case becomes approximately O(k^w × n) instead of O(n).

Key Takeaway: Wildcard matching in tries works by recursively exploring all possible child branches when a wildcard is encountered, transforming a single-path search into a multi-path exploration that can match multiple patterns simultaneously.