AlgoMaster Logo

Wildcard Matching

Last Updated: March 28, 2026

hard
5 min read

Understanding the Problem

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

The '?' wildcard is straightforward: it matches exactly one character, no matter what that character is. Regular characters must match exactly. The real challenge boils down to: when we see a '*', how many characters from s should it consume?

The key observation is that this decision, how many characters each '*' eats, creates overlapping subproblems. If we try all possibilities naively, we'll solve the same subproblem many times. That's the classic signal for dynamic programming.

Key Constraints:

  • 0 <= s.length, p.length <= 2000 -> Both strings can be up to 2000 characters. An O(n * m) solution would mean up to 4 million operations, which is very comfortable.
  • s contains only lowercase English letters -> No wildcards in s, only in p. This simplifies our matching logic.
  • 0 <= s.length -> Either string can be empty. We need to handle the case where s is empty but p is "***" (which should return true).

Approach 1: Recursion with Memoization

Intuition

The most natural way to think about this problem is recursively. 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 match s[i] exactly.
  • If p[j] is '?', it matches any single character, so we move both pointers forward.
  • If p[j] is '*', here's where it gets interesting. The '*' can match zero characters (skip it, advance j) or match one character (consume s[i], keep j at '*' so it can potentially match more).

This branching on '*' means we might explore the same (i, j) pair multiple times through different paths. That's exactly when memoization helps. We cache results for each (i, j) pair so we never recompute them.

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 approach is intuitive but has overhead from function calls and hash map lookups. Can we fill the same DP table iteratively, eliminating recursion overhead and stack depth concerns?

Approach 2: Bottom-Up Dynamic Programming

Intuition

Instead of recursing top-down with memoization, we can 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 subproblems to larger ones.

The transitions are the same as in the recursive approach, just expressed differently:

  • If p[j-1] is a letter or '?', then dp[i][j] = dp[i-1][j-1] when the characters match.
  • 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, but each row only depends on the current and previous row. Can we avoid the table entirely with a greedy strategy that uses O(1) space?

Approach 3: Greedy with Backtracking

Intuition

Instead of DP, we can use a greedy approach that handles '*' by remembering the last star's position and backtracking when we hit a dead end.

The idea: scan through s and p simultaneously. When characters match (or pattern has '?'), advance both pointers. When we hit a '*', record its position in the pattern and the current position in s. Then try matching '*' with zero characters first by advancing only the pattern pointer.

If we later hit a mismatch, we backtrack to the last '*' we recorded and try making it match one more character from s. We keep doing this until either we find a complete match or exhaust all possibilities.

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