Wildcard Matching

The reliable way to solve wildcard matching is to model it as reachability over two consumed prefixes—not as an improvised backtracking fight with *.

The contract and the DP signal

Given a text s and pattern p:

• A literal matches the same character.
• ? matches exactly one arbitrary character.
• * matches zero or more characters.
• The match is anchored: the pattern must account for all of s.

The constraints allow both strings to have length up to 2000. The text contains lowercase English letters; the pattern contains lowercase letters, ?, and *.

The phrase “all of s” is the first constraint to protect. A pattern that matches only a prefix is still wrong if text remains unmatched.

The dynamic-programming signal is structural:

1. Progress through the text matters.
2. Progress through the pattern matters.
3. A * can create several valid alignments between those positions.

That gives us two coordinates: how much text has been consumed and how much pattern has been consumed.

This resembles regular-expression matching, but the semantics are different. Here, * is already the arbitrary-sequence symbol. It is not a modifier attached to the preceding token. Mixing those contracts produces the wrong recurrence.

Why naive branching repeats work

A direct recursive matcher can track positions (i, j):

• If p[j] is a literal or ?, advance both positions.
• If p[j] == '*', branch:
  • Treat * as empty and advance the pattern.
  • Let * consume one text character and advance the text.

The second branch keeps j unchanged. The same star remains active and may consume another character.

That branching is logically correct, but uncached recursion repeatedly reaches the same pair of positions. Different allocations of characters to earlier stars can converge on the same remaining text and pattern.

For example:

s = "adceb"
p = "*a*b"

The first * might consume nothing, a, ad, or more. The second * might consume nothing or absorb characters before the final b. Those search paths can eventually ask the same question:

Do these consumed text and pattern prefixes match?

Dynamic programming stores the answer for each pair of progress coordinates once.

Define the two-prefix state

Let:

dp[i][j] = whether s[:i] matches p[:j]

where:

• 0 <= i <= m, with m = len(s)
• 0 <= j <= n, with n = len(p)

The indices are prefix lengths, not character positions.

Therefore:

• s[:0] is empty.
• p[:0] is empty.
• The newly added text character at state i is s[i - 1].
• The newly added pattern symbol at state j is p[j - 1].

The invariant is:

If dp[i][j] is true, the first i text characters and first j pattern symbols form a complete legal match. Nothing outside either prefix has been considered.

The answer is:

dp[m][n]

That terminal cell is true only when both complete inputs have been consumed. A true cell such as dp[m][j] for j < n is insufficient because the remaining pattern may still contain literals. Likewise, dp[i][n] is false when text remains.

A suffix-based memoized formulation is equivalent, but I prefer the prefix table here. Its dependencies are visible, and the anchored terminal state is impossible to overlook.

Derive the recurrence from legal actions

The safest way to derive this wildcard matching DP is to ask what the newest pattern symbol is allowed to do.

Literal or question mark

Suppose p[j - 1] is a literal or ?.

It accounts for exactly one text character. The new text character must match either because:

• the literal equals s[i - 1], or
• the pattern symbol is ?.

The earlier prefixes must already match:

dp[i][j] = dp[i - 1][j - 1]

when:

p[j - 1] == s[i - 1] or p[j - 1] == "?"

Otherwise:

dp[i][j] = False

Both prefixes advance by one, so the dependency is diagonal.

Asterisk: match the empty sequence

If:

p[j - 1] == "*"

the star may match zero characters. It consumes no text, so we move past the star in the pattern:

dp[i][j - 1]

This is a leftward dependency.

Asterisk: consume one more character

The star may also consume the newest text character while remaining available for additional characters.

The earlier state is therefore:

dp[i - 1][j]

The text prefix becomes shorter, but the pattern prefix still includes the active star. This is an upward dependency.

Combining the two legal interpretations:

dp[i][j] = dp[i][j - 1] or dp[i - 1][j]

for a star.

No diagonal term is needed. The two existing branches already cover every possibility:

• Empty branch: skip the star.
• Consume branch: consume one character and keep the star active.

The table geometry records the semantics:

• Ordinary symbols move diagonally.
• * can move left or up.

If an implementation treats * as exactly one character, only empty, or diagonal-only, it has deleted a legal interpretation.

Initialize empty prefixes

The base cases are part of the algorithm. They are not boilerplate.

Both prefixes empty

An empty pattern matches an empty text:

dp[0][0] = True

Nonempty text and empty pattern

An empty pattern cannot match nonempty text:

dp[i][0] = False    for i > 0

Empty text and a pattern prefix

An empty text matches a pattern prefix only when every symbol in that prefix is *.

For example, with:

p = "***a*"

the empty text matches:

""
"*"
"**"
"***"

It does not match "***a" because the literal a requires one text character. A later star cannot repair a literal that was never matched.

Initialize the first row with:

dp[0][j] = dp[0][j - 1] and p[j - 1] == "*"

The truth carries across consecutive stars and stops permanently at the first non-star.

This handles empty inputs, all-star patterns, leading stars, and trailing stars.

Prove full-match correctness

We can prove the recurrence by induction over increasing prefix lengths.

Literal and ?

For a literal or ?, the newest pattern symbol must match exactly one newest text character. No other action is legal:

• It cannot consume zero text characters.
• It cannot consume multiple text characters.
• It cannot leave the pattern position unchanged.

Therefore, dp[i][j] is true exactly when the new symbols match and dp[i - 1][j - 1] is true.

The transition is necessary and sufficient.

*

For a star, every legal match falls into one of two exhaustive cases:

1. The star consumes no text character.
   The match must already be valid after skipping it: dp[i][j - 1].

2. The star consumes the newest text character.
   The star remains active, so the earlier state is dp[i - 1][j].

Conversely, either predecessor creates a valid match:

• A valid dp[i][j - 1] state extends by assigning the star an empty sequence.
• A valid dp[i - 1][j] state extends by assigning the star s[i - 1].

The base cases correctly describe empty prefixes. Every transition preserves the prefix invariant. Therefore, dp[m][n] is true exactly when the entire text matches the entire pattern.

The DP table is not merely a cache of guesses. It is a reachability proof.

Trace s = "adceb" and p = "*a*b"

Use pattern-column indices:

j:      0    1    2    3    4
p[:j]: ""   "*"  "*a"  "*a*" "*a*b"

The full table is:

i	s[:i]	dp[i][0]	dp[i][1]	dp[i][2]	dp[i][3]	dp[i][4]
0	""	T	T	F	F	F
1	"a"	F	T	T	T	F
2	"ad"	F	T	F	T	F
3	"adc"	F	T	F	T	F
4	"adce"	F	T	F	T	F
5	"adceb"	F	T	F	T	T

Now inspect the important transitions.

Leading star

• dp[0][1] = dp[0][0]: skip the leading star; it consumes nothing.
• dp[1][1] = dp[0][1]: the star consumes a.
• dp[2][1] = dp[1][1]: the same star consumes d.
• The same upward dependency keeps dp[3][1], dp[4][1], and dp[5][1] true.

The star remains active because the pattern index stays at j = 1.

Literal a

At dp[1][2], the pattern symbol is a and the text symbol is a:

dp[1][2] = dp[0][1] = True

At dp[2][2], the newest text symbol is d, so the literal fails:

dp[2][2] = False

This is why dp[2][1] being true does not automatically make dp[2][2] true. The literal must align with the exact newest character.

Second star

At dp[1][3], the second star skips itself:

dp[1][3] = dp[1][2] = True

At dp[2][3], it can consume d:

dp[2][3] = dp[1][3] = True

The same consume branch carries truth through dp[3][3] and dp[4][3].

Final literal b

The final b matches the final text character:

dp[5][4] = dp[4][3] = True

The path reaches the bottom-right cell, so the complete match succeeds.

Two failure cases test the boundaries:

s = "aa"
p = "a"

dp[1][1] is true, but dp[2][1] is false. A prefix match is not a full match.

s = "cb"
p = "?a"

? consumes c, but the final literal a does not match b. The path dies before the terminal cell.

Implement the full table in Python

def is_match(s: str, p: str) -> bool:
    m, n = len(s), len(p)

    # dp[i][j] means s[:i] matches p[:j].
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True

    # Empty text matches only a prefix made entirely of '*'.
    for j in range(1, n + 1):
        dp[0][j] = dp[0][j - 1] and p[j - 1] == "*"

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            pattern_char = p[j - 1]

            if pattern_char == "*":
                # '*' matches empty, or consumes one text character.
                dp[i][j] = dp[i][j - 1] or dp[i - 1][j]

            elif pattern_char == "?" or pattern_char == s[i - 1]:
                # A literal or '?' consumes one character from each input.
                dp[i][j] = dp[i - 1][j - 1]

            # Otherwise dp[i][j] remains False.

    return dp[m][n]

Every index in the code has a named obligation:

• dp[i][j] represents the two consumed prefixes.
• s[i - 1] and p[j - 1] are the newly added symbols.
• dp[i - 1][j - 1] is the diagonal predecessor for one-to-one matching.
• dp[i][j - 1] skips a star.
• dp[i - 1][j] consumes another character with the same star.

The common indexing error is changing j in the consume branch. If * consumes text, the pattern index must stay fixed. Decrementing j accidentally discards the star and prevents it from consuming again.

Compress the table to one dimension

The full table uses O(mn) auxiliary space, but each row depends only on:

• The previous row's value at column j.
• The current row's value at column j - 1.
• The previous row's diagonal value at column j - 1.

That allows O(n) space:

def is_match_compressed(s: str, p: str) -> bool:
    m, n = len(s), len(p)

    # Before processing row i, dp[j] represents the previous row:
    # whether s[:i - 1] matches p[:j].
    dp = [False] * (n + 1)
    dp[0] = True

    for j in range(1, n + 1):
        dp[j] = dp[j - 1] and p[j - 1] == "*"

    for i in range(1, m + 1):
        # dp[0] is the current row's value for a nonempty text
        # against an empty pattern.
        dp[0] = False

        # old_diagonal represents the previous row's dp[j - 1].
        old_diagonal = False

        for j in range(1, n + 1):
            old_current = dp[j]  # Previous row's dp[j].

            if p[j - 1] == "*":
                # old_current = dp[i - 1][j]
                # dp[j - 1] = dp[i][j - 1]
                dp[j] = old_current or dp[j - 1]

            elif p[j - 1] == "?" or p[j - 1] == s[i - 1]:
                # old_diagonal = dp[i - 1][j - 1]
                dp[j] = old_diagonal

            else:
                dp[j] = False

            old_diagonal = old_current

    return dp[n]

The update order is left to right because the star recurrence needs the current row's left value. Before overwriting dp[j], save its old value for the next iteration's diagonal.

The invariant during the inner loop is:

• dp[j] before assignment is the previous row's dp[i - 1][j].
• dp[j - 1] after assignment is the current row's dp[i][j - 1].
• old_diagonal is the previous row's dp[i - 1][j - 1].

Compression is safe only because those three logical values remain available at the moment each transition is computed. I would derive and debug the full table first, then compress. An optimization that hides the dependency graph is a liability until the graph is already understood.

Complexity and edge cases

There are (m + 1)(n + 1) states, and each state performs constant work.

For the full table:

Time:  O(mn)
Space: O(mn)

For the compressed implementation:

Time:  O(mn)
Space: O(n)

Here n is the pattern length because the one-dimensional array stores pattern columns.

Test the obligations directly:

• s = "", p = "" → true.
• s = "", p = "***" → true.
• s = "", p = "*a*" → false.
• s = "abc", p = "" → false.
• s = "abc", p = "***" → true.
• s = "abc", p = "a?c" → true.
• s = "abc", p = "a*d" → false.
• s = "aa", p = "a" → false because matching is anchored.
• s = "adceb", p = "*a*b" → true.

The recognition rule

A two-dimensional table is justified when both coordinates carry meaning. Here, correctness depends on the exact amount of text consumed and the exact amount of pattern consumed. The star allows those coordinates to advance at different rates.

The reusable move is:

When a problem progresses through two structures and one operation can advance one coordinate while holding the other, model the pair of progress coordinates.

Then:

1. Define the state using consumed prefixes.
2. Enumerate the ambiguous symbol's legal actions.
3. Map each action to a predecessor.
4. Initialize empty prefixes explicitly.
5. Return only the state that consumes both inputs.

For wildcard matching, the two star actions are simple:

• Skip *.
• Let * consume one character and remain active.

Name those actions before writing code. The recurrence then stops looking like a memorized wildcard formula and becomes what it really is: a reachability proof over a grid.