425. Does the Pattern Match
A pattern may contain two special characters:
? matches exactly one character
* matches any run of characters, including none
Print yes if the pattern matches the WHOLE string and no otherwise.
? is easy: it consumes one character and the recursion moves on. * is the
whole problem, because it may consume any number of characters and the right
number depends on what comes after it.
Matching greedily fails. On s = adceb with p = *a*b, letting the first *
swallow as much as possible leaves nothing for a. Letting it swallow nothing
works. No local rule decides this, so both options must be available:
match(i, j):
p[j] == '*' -> match(i+1, j) the star eats s[i]
or match(i, j+1) the star stops here
p[j] == '?' -> match(i+1, j+1)
else -> s[i] == p[j] and match(i+1, j+1)
The two-way branch on * is what makes the naive recursion exponential and
memoisation essential: the pair (i, j) is reached along many different paths
with the same remaining work.
The base cases are where this goes wrong. String exhausted and pattern
exhausted is a match. String exhausted with pattern left is a match only if
everything remaining is *. Pattern exhausted with string left is never a
match.
Constraints - `1 ≤ length of s ≤ 1000` - `1 ≤ length of p ≤ 1000` - `s` is lowercase English letters. - `p` is lowercase English letters, `?` and `*`.
Input
The first line contains the string s.
The second line contains the pattern p.
Output
Print yes if the pattern matches the entire string, or no otherwise.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.