LeetCode Q44: Wildcard Matching

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

I implement a DP solution, but the code didn't pass all test cases of leetcode due to running over the memory limit of leetcode.

My code is given as below:

This question can actually be solved using greedy algorithm which takes only O(s.length()+p.length()) time and constant space. For exact solution please refer to leetcode forum at:
https://leetcode.com/discuss/10133/linear-runtime-and-constant-space-solution.

The method, try to match as many common characters of s and p, and when match is failed at current location, it roll back and to last '*' location, and increment pointer of s by one. It will roll back again and make the increment if the match still can not be found.

For each element in s
If *s==*p or *p == ? which means this is a match, then goes to next element s++ p++.
If p=='*', this is also a match, but one or many chars may be available, so let us save this *'s position and the matched s position.
If not match, then we check if there is a * previously showed up,
       if there is no *,  return false;
       if there is an *,  we set current p to the next element of *, and set current s to the next saved s position.

For quick reference, the code is given in below: