Regular Expression Matching
A pattern may contain two special characters:
. matches exactly ONE character
* means "zero or more of the element IMMEDIATELY BEFORE it"
Print yes if the pattern matches the WHOLE string, or no otherwise. The pattern is
always valid: it never begins with * and never has two * in a row.
s = aa, p = a -> no
s = aa, p = a* -> yes
s = ab, p = .* -> yes . repeated twice
s = aab, p = c*a*b -> yes c zero times, a twice, then b
## How this differs from problem 507
In wildcard matching, * stands alone and absorbs characters by itself. Here * is a
QUANTIFIER: it modifies the element before it, and a* is one unit meaning "any number of
as".
The consequence is that the pattern must be read TWO characters at a time whenever the
second is a *, and the two problems therefore have different recurrences despite looking
alike. Mixing them up is the usual failure.
## The grid
dp[i][j] = does the first i characters of s match the first j characters of p
For a plain element, meaning p[j-1] is a letter or .:
dp[i][j] = dp[i-1][j-1] if p[j-1] is . or equals s[i-1]
For p[j-1] == '*', the unit is p[j-2] p[j-1]:
dp[i][j] = dp[i][j-2] the unit matches ZERO times
OR dp[i-1][j] if p[j-2] matches s[i-1] the unit matches ONE MORE time
## Reading the two branches
dp[i][j-2] skips the whole two-character unit, which is the "zero times" case. Skipping
only one character instead of two is the single most common bug here, and it makes a*
behave like a?.
dp[i-1][j] consumes one character of s and keeps the unit available, which is the "one
more time" case. It is guarded by whether p[j-2] actually matches s[i-1], because the
star repeats THAT element and nothing else.
s = aaa, p = a*a answers yes, and it needs the star to take two and the final a to
take one. s = abb, p = a*b*c answers no: both stars can take zero, and there is still
no c.
## The first row
dp[0][j] asks whether the empty string matches a pattern prefix. That is true when the
prefix is a sequence of units each of which can match zero times, so:
dp[0][0] = true
dp[0][j] = dp[0][j-2] when p[j-1] is * and j >= 2
and false otherwise. The step of TWO is what makes c*a*b reachable from the empty string
for its first four characters, and a step of one gives the wrong answer on
s = aab, p = c*a*b.
## Cost
Time O(n m). Space O(n m), reducible to O(m).