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.