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.