Wildcard Matching Solution

Problem

Given a string s and a pattern p, determine if p matches the entire string s. The pattern supports two wildcards: ? matches exactly one character, and * matches any sequence of characters, including the empty sequence.

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first * matches the empty string, a matches a, the second * matches dc, and b matches b.

A counter-example: s = "acdcb", p = "a*c?b" → false. The ? must match exactly one character, so a*c matches acd, ? matches c, but b fails against nothing remaining in s.

Intuition

At every step you're deciding how to align characters in s with tokens in p. Regular characters and ? are rigid — they consume exactly one character from each side. The difficulty is *, which can consume zero, one, or many characters from s. The insight is that for any *, you can express its optimal matching as: either it covers nothing (move past it in p) or it covers one more character from s. Repeating that choice over all positions gives a clean 2D recurrence. An alternative is to track the last * seen and backtrack greedily whenever a later mismatch occurs.

Approach 1 — Dynamic Programming

Build a 2D boolean table where dp[i][j] is true if the first i characters of s are fully matched by the first j characters of p. The * case splits into two sub-problems: the star matches nothing (inherit dp[i][j-1]) or the star extends to cover one more character of s (inherit dp[i-1][j]).

Create dp of size (m+1) × (n+1), all false. Set dp[0][0] = true.
Fill the first row: dp[0][j] = true while p[j-1] == '*' (a prefix of all stars matches an empty string).
For each i from 1 to m and each j from 1 to n:
- If p[j-1] == '*': dp[i][j] = dp[i][j-1] or dp[i-1][j]
- Else if p[j-1] == '?' or p[j-1] == s[i-1]: dp[i][j] = dp[i-1][j-1]
Return dp[m][n].

1def is_match(s: str, p: str) -> bool:
2    m, n = len(s), len(p)
3    dp = [[False] * (n + 1) for _ in range(m + 1)]
4    dp[0][0] = True
5
6    # consecutive leading '*' characters match the empty string
7    for j in range(1, n + 1):
8        if p[j - 1] == '*':
9            dp[0][j] = dp[0][j - 1]
10
11    for i in range(1, m + 1):
12        for j in range(1, n + 1):
13            if p[j - 1] == '*':
14                # star matches empty (advance j) OR extends to cover s[i-1] (advance i)
15                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
16            elif p[j - 1] == '?' or p[j - 1] == s[i - 1]:
17                dp[i][j] = dp[i - 1][j - 1]
18
19    return dp[m][n]

Time: O(m · n) — fills every cell of the table exactly once.
Space: O(m · n) — the full 2D DP table.

Approach 2 — Greedy with Star Tracking

Instead of a table, walk s and p with two pointers. When a * is encountered, record where it is in p and which index of s it currently covers (zero characters at first). On any mismatch, backtrack to the most recent * and let it absorb one more character from s.

Initialize i = j = 0 and star_j = star_i = -1 (no star seen yet).
While i < len(s):
- If p[j] is a literal or ? that matches s[i]: advance both pointers.
- Else if p[j] == '*': save star_j = j and star_i = i, advance only j (star absorbs nothing yet).
- Else if a star was seen (star_j != -1): increment star_i, reset i = star_i and j = star_j + 1.
- Else: return false (no star to fall back on).
After exhausting s, skip any remaining * in p.
Return true only if j has reached the end of p.

1def is_match(s: str, p: str) -> bool:
2    i = j = 0
3    star_j = star_i = -1  # last '*' in pattern and its current match position in s
4
5    while i < len(s):
6        if j < len(p) and (p[j] == '?' or p[j] == s[i]):
7            i += 1
8            j += 1
9        elif j < len(p) and p[j] == '*':
10            star_j = j      # bookmark the star's location in pattern
11            star_i = i      # star currently covers zero chars; s[i] not yet consumed
12            j += 1
13        elif star_j != -1:
14            # extend the last '*' to cover one more character of s
15            star_i += 1
16            i = star_i
17            j = star_j + 1
18        else:
19            return False
20
21    # skip any trailing '*' characters (they can match the empty remainder)
22    while j < len(p) and p[j] == '*':
23        j += 1
24    return j == len(p)

Time: O(m · n) worst case — each * can cause s to be rescanned.
Space: O(1) — only a constant number of integer pointers.

Complexity Summary

Approach	Time	Space	When to use
Dynamic Programming	O(m · n)	O(m · n)	Clearest reasoning; preferred in interviews for explainability
Greedy with Star Tracking	O(m · n)	O(1)	When space is constrained or you want the simplest code

Common Mistakes

Confusing ? with * — ? must match exactly one character; it cannot match zero. A pattern like ? never matches an empty string.
Wrong dp[0][j] initialization — Only a contiguous run of * characters at the start matches the empty string. As soon as any non-* appears, subsequent dp[0][j] should remain false. Many implementations incorrectly mark dp[0][j] = true for all j or forget this row entirely.
dp[i][j] = dp[i-1][j] only for * — The recurrence dp[i][j] |= dp[i-1][j] is specific to the star case (extending coverage). Applying it for ? or literal characters is wrong.
Greedy: advancing star_i instead of resetting i — On backtrack, you must set both i = star_i and j = star_j + 1; forgetting to reset j leaves the pattern pointer in the wrong place.
Not consuming trailing *s after exhausting s — Patterns like "a*" applied to "a" correctly return true, but only if you skip the trailing star after the loop ends. Returning j == len(p) without this cleanup fails those cases.

Wildcard Matching — Solution