AlgoMaster Logo

Wildcard Matching

hardFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We need to check if pattern p fully matches string s. The hard character is '*' because it can match any sequence, including nothing at all. A single '*' could consume zero characters, one character, or the entire remaining string. This branching is the source of the difficulty.

The '?' wildcard matches exactly one character, whatever that character is. Regular characters must match exactly. The open question is: when we see a '*', how many characters from s should it consume?

The number of characters one '*' consumes changes what the rest of the pattern has to match. Trying every possibility by brute force re-solves the same suffix-against-suffix comparison many times, which is the signal for dynamic programming.

Key Constraints:

  • 0 <= s.length, p.length <= 2000 means an O(n * m) solution is at most about 4 million operations, well within limits, so we do not need anything faster than quadratic.
  • s contains only lowercase English letters, so wildcards appear only in p. We never have to interpret a wildcard on the string side.
  • Either string can be empty. An empty s against a pattern of only stars ("***") must return true, since each star can match the empty sequence.

Approach 1: Recursion with Memoization

Intuition

Define the problem recursively: does the suffix s[i:] match the suffix p[j:]? We compare characters from left to right. At each step, we look at s[i] and p[j]:

  • If p[j] is a regular character, it must equal s[i], and we advance both pointers.
  • If p[j] is '?', it matches any single character, so we advance both pointers.
  • If p[j] is '*', we branch. The '*' can match zero characters (skip it, advance j) or match one character (consume s[i], keep j at the '*' so it can match more).

The branch on '*' lets the same (i, j) pair be reached through different paths. Caching the result for each (i, j) pair turns the exponential recursion into one that does work proportional to the number of distinct pairs.

Algorithm

  1. Define a recursive function match(i, j) that returns whether s[i:] matches p[j:].
  2. Base cases: if both i and j are past the end, return true. If only j is past the end but s has characters left, return false. If only i is past the end, return true only if all remaining characters in p are '*'.
  3. If p[j] is '*', try two branches: match(i, j+1) (star matches nothing) or match(i+1, j) (star matches s[i] and stays).
  4. If p[j] is '?' or matches s[i], recurse with match(i+1, j+1).
  5. Otherwise, return false.
  6. Memoize results in a 2D table keyed by (i, j).

Example Walkthrough

1Start: match(0,0), p[0]='*', try match(0,1) and match(1,0)
0
a
i=0
1
d
2
c
3
e
4
b
1/6

Code

The recursive version carries function-call overhead and, in some languages, hash-map lookups. The next approach fills the same table iteratively, which removes the recursion stack and the call overhead.

Approach 2: Bottom-Up Dynamic Programming

Intuition

Instead of recursing top-down with memoization, we build the answer bottom-up. Define dp[i][j] as whether the first i characters of s match the first j characters of p. We fill this table from smaller prefixes to larger ones.

The transitions mirror the recursive cases, indexed by prefix length rather than suffix position:

  • If p[j-1] is a letter or '?', then dp[i][j] = dp[i-1][j-1] when the characters match (and false otherwise).
  • If p[j-1] is '*', then dp[i][j] = dp[i][j-1] (star matches empty) OR dp[i-1][j] (star matches one more character from s).

Algorithm

  1. Create a 2D boolean table dp of size (n+1) x (m+1), initialized to false.
  2. Set dp[0][0] = true.
  3. Fill the first row: dp[0][j] = true if p[0..j-1] is all stars.
  4. Fill the table row by row. For each cell dp[i][j]:
    • If p[j-1] == '*': dp[i][j] = dp[i][j-1] || dp[i-1][j]
    • If p[j-1] == '?' || p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]
  5. Return dp[n][m].

Example Walkthrough

1Initialize: dp[0][0]=T, dp[0][1]=T (p[0]='*' matches empty)
0
a
1
d
2
c
3
e
4
b
1/6

Code

The DP approach uses O(n * m) space. The next approach drops the table entirely and matches greedily with O(1) extra space, backtracking only at the most recent star.

Approach 3: Greedy with Backtracking

Intuition

Instead of DP, we scan s and p together and handle '*' by remembering the last star's position, backtracking to it when a later mismatch occurs.

The procedure: when characters match (or the pattern has '?'), advance both pointers. When we reach a '*', record its pattern position and the current position in s, then advance only the pattern pointer, which tries matching the star against zero characters first.

On a later mismatch, reset the pattern pointer to just past the recorded star and let the star consume one more character of s. We repeat this until we either consume all of s or run out of stars to extend.

Algorithm

  1. Initialize four variables: sIdx = 0 (current position in s), pIdx = 0 (current position in p), starIdx = -1 (position of last '*' in p), matchIdx = 0 (position in s where we started matching after the last '*').
  2. While sIdx < len(s):
    • If p[pIdx] matches s[sIdx] (same character or '?'), advance both pointers.
    • If p[pIdx] == '*', record starIdx = pIdx and matchIdx = sIdx, then advance pIdx (try matching star with zero characters).
    • Otherwise, if we have a recorded star, backtrack: reset pIdx to starIdx + 1, increment matchIdx (star now matches one more character), and set sIdx = matchIdx.
    • If none of the above, return false.
  3. After the loop, skip any remaining '*' characters in p.
  4. Return true if pIdx == len(p).

Example Walkthrough

1Initialize: sIdx=0, pIdx=0, starIdx=-1
0
a
sIdx
1
d
2
c
3
e
4
b
1/8

Code