507. Wildcard Matching

A pattern may contain two special characters:

? matches exactly ONE character * matches ANY sequence of characters, including the empty one

Print yes if the pattern matches the WHOLE string, or no otherwise.

s = adceb, p = *a*b -> yes s = acdcb, p = a*c?b -> no s = aa, p = a -> no the match must cover the whole string

## Why recursion alone is too slow

Expanding * by trying every length it could consume gives a branching recursion, and a pattern like *a*a*a*a against a long string of as explores exponentially many splits that all reach the same place.

The saving is the usual one: after some decisions, all that matters is HOW MUCH of each side has been consumed, not which splits got you there. That is two indices, so the table is a grid.

## The grid

dp[i][j] = does the first i characters of s match the first j characters of p

p[j-1] is a letter or ? -> dp[i][j] = dp[i-1][j-1] if the characters agree p[j-1] is * -> dp[i][j] = dp[i-1][j] OR dp[i][j-1]

## The star rule, which is the whole problem

dp[i-1][j] the star absorbs s[i-1] and stays available for more dp[i][j-1] the star matches nothing more and is finished with

Two branches, not a loop over lengths. That single substitution is what turns the exponential recursion into O(n m): "the star eats one more character" and "the star is done" between them cover every possible length, because eating one more character is itself a state that can eat one more again.

Collapsing a loop over lengths into a single "one more step" branch is the move worth remembering, and it appears in almost every pattern-matching DP.

## The first row, which is the usual bug

dp[0][j] asks whether the empty string matches the first j pattern characters. That is true only when every one of those characters is a *:

dp[0][0] = true dp[0][j] = dp[0][j-1] when p[j-1] is *, otherwise false

Leaving the first row as all-false makes any pattern starting with * fail, and s = adceb, p = *a*b answers no instead of yes. Leaving it all-true makes almost everything match.

The first COLUMN needs nothing: dp[i][0] is false for i > 0, since an empty pattern cannot cover a non-empty string.

## What the tests pin down

s = aa, p = a answers no. The match must cover the whole string, not a prefix of it, which is why the answer is read at dp[n][m] and not from any row.

s = abc, p = ? answers no for the same reason from the other direction.

s = mississippi, p = m??*ss*?i*pi answers no, and it is the long case: a pattern with three stars where the match nearly works.

## Cost

Time O(n m). Space O(n m), reducible to O(m) with two rows.

Constraints - `1 ≤ length of s ≤ 2000` - `1 ≤ length of p ≤ 2000` - `s` contains only lowercase letters - `p` contains lowercase letters, `?` and `*`