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]=trueiftext[0..i-1]matchespattern[0..j-1]
State Transitions
- Base case:
dp[0][0] = true(empty matches empty) - Empty text, pattern with
*:dp[0][j]depends on previous*matches - Character match or
?:dp[i][j] = dp[i-1][j-1]if characters match or pattern has? *wildcard:dp[i][j] = dp[i-1][j](match one more char) ORdp[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.