Course contentsShow
← Computer Science
Lesson 942 of 2,87222. Dynamic ProgrammingFree lesson

Wildcard Pattern Matching

Match string against pattern with wildcards '?' and '*' using 2D DP state table.

Wildcard Pattern Matching

What you'll learn: How to determine if a string matches a pattern containing wildcards using a 2D dynamic programming table.


The Problem

You need to check if a text string matches a pattern that may contain two special wildcards:

  • ? matches exactly one character
  • * matches zero or more characters (any sequence)

For example, "ab*d?" matches "abcde" but not "abde".

Why Dynamic Programming?

This problem has overlapping subproblems and optimal substructure. Whether text[0..i] matches pattern[0..j] depends on smaller subproblems we've already solved. Recursion would recompute the same comparisons many times—DP stores those results.

The 2D State Table

Create a table dp[i][j] where:

  • i = characters processed from text (0 to len(text))
  • j = characters processed from pattern (0 to len(pattern))
  • dp[i][j] = true if text[0..i-1] matches pattern[0..j-1]

State Transitions

  1. Base case: dp[0][0] = true (empty matches empty)
  2. Empty text, pattern with *: dp[0][j] depends on previous * matches
  3. Character match or ?: dp[i][j] = dp[i-1][j-1] if characters match or pattern has ?
  4. * wildcard: dp[i][j] = dp[i-1][j] (match one more char) OR dp[i][j-1] (skip the *)

Think of it like filling a grid: each cell answers "do these prefixes match?" based on neighbors you've already computed.

Building Bottom-Up

Start at dp[0][0] and fill row by row, column by column, until you reach dp[len(text)][len(pattern)]—your final answer.

Key Takeaway: Wildcard pattern matching uses a 2D DP table where dp[i][j] tracks whether text up to position i matches pattern up to position j, with transitions handling ?, *, and exact character matches.