CodeWithYash

Intermediate · Module 15 · Lesson 2

Wildcard trie search

Branch when a pattern can match multiple edges.

15–25 min readLesson 84 of 123

Lesson 84 of 123

1d streak

Theory lesson · Step-by-step

Understand Wildcard trie search

Branch when a pattern can match multiple edges.

Worked approach

Trace the reasoning step by step

  1. 1Identify whether Wildcard trie search is driven by characters or ordered boundaries.
  2. 2Create the searchable prefix path or sort interval events by the required key.
  3. 3Advance one character or event while preserving terminal and overlap state.
  4. 4Branch only for valid wildcard edges, or merge only when ranges overlap.
  5. 5Test empty prefixes, touching intervals, nested ranges, and equal-time events.

Concrete example

Match pattern "c.t" against words "cat" and "cut".

  1. 1Follow c.
  2. 2Wildcard branches through a and u.
  3. 3Both paths reach terminal t.

The wildcard pattern matches both words.

What must remain true (Loop Invariant)

For Wildcard trie search, the active prefix path or ordered interval frontier represents exactly the input processed so far without losing overlap information.

Cost Model

Complexity & Trade-offs

Pattern search
O(branching^wildcards × length)
O(depth)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Autocomplete, dictionary prefixes, wildcard matching, overlap, and scheduling.
  • Sharing common string prefixes.
  • Reducing range problems to ordered start/end events.

Common mistakes

  • Forgetting terminal markers in a trie.
  • Treating touching intervals as overlap without checking the problem convention.
  • Processing equal-time events in the wrong order.

Practice prompts

  • Reproduce the worked Wildcard trie search example without looking at the trace.
  • Change one input condition and explain whether the Wildcard trie search invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.