Problem Statement

Wildcard Matching

You have a text string s and a pattern p. The pattern can hold two special wildcard characters. A wildcard is just a symbol that stands in for other characters. Here '?' matches any single character (one character, no more, no less), and '*' matches any run of characters including no characters at all. Your job is to say whether the whole pattern matches the whole string. We will solve this with dynamic programming, which is a fancy way of saying we break the problem into tiny yes or no questions, write each answer in a grid, and reuse those answers so we never solve the same little question twice. Here the question we fill in is dp[i][j]: does the first i characters of s match the first j characters of p?

hardDynamic ProgrammingStringDynamic ProgrammingTime: O(m*n) · Space: O(m*n)

Signals to notice

wildcard pattern matching? = one char, * = any sequence2D DP

Brute force first

Recursive without memo — exponential.

The key insight

dp[i][j] = s[0..i-1] matches p[0..j-1]. For *: dp[i][j] = dp[i][j-1] || dp[i-1][j]. For ?: dp[i-1][j-1]. O(mn).

Trace it on `s="acdcb", p="ac?b" (p = a, , c, ?, b)`

Init row0: dp[0][0]=T; p[0]='a'≠'*' so dp[0][1..5]=F (empty s only matches empty p)
i=1 (s='a'): p[0]='a'==s -> dp[1][1]=dp[0][0]=T; p[1]='*' -> dp[1][2]=dp[0][2] or dp[1][1]=T; rest of row F
i=2 (s='c'): p[1]='*' -> dp[2][2]=dp[1][2] or dp[2][1]=T; p[2]='c'==s -> dp[2][3]=dp[1][2]=T; dp[2][4],dp[2][5]=F
i=3 (s='d'): dp[3][2]=T via '*'; p[2]='c'≠'d' -> dp[3][3]=F; p[3]='?' -> dp[3][4]=dp[2][3]=T; p[4]='b'≠'d' -> dp[3][5]=F
i=4 (s='c'): dp[4][2]=T via '*'; p[2]='c'==s -> dp[4][3]=dp[3][2]=T; p[3]='?' -> dp[4][4]=dp[3][3]=F; dp[4][5]=F
i=5 (s='b'): dp[5][2]=T via '*'; p[2]='c'≠'b' -> dp[5][3]=F; p[3]='?' -> dp[5][4]=dp[4][3]=T; p[4]='b'==s -> dp[5][5]=dp[4][4]=F
Return dp[5][5] = False

What must stay true

* has two choices: match empty (dp[i][j-1]) or match one more char (dp[i-1][j]). ? matches any single char.

Shape of the loop

dp[0][0] = true
for j in 1..n: dp[0][j] = dp[0][j-1] and p[j-1]=='*'
for i in 1..m, for j in 1..n:
  if p[j-1]=='*':            dp[i][j] = dp[i-1][j] or dp[i][j-1]
  elif p[j-1]=='?' or p[j-1]==s[i-1]: dp[i][j] = dp[i-1][j-1]
return dp[m][n]

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Confusing * here vs regex * — wildcard * matches any sequence independently.

Dynamic Programming Pattern