Wildcard Matching [Leetcode]

Implement wildcard pattern matching with support for '?' and '*'.

'?' 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

Solution: the first method is recursion, but I got TLE. Then I tried DP; got MLE; then I reduced the space requirement to O(n), where n is the length of string S. I found the solution 3 online; check here.

   /*******************************SOLUTION 1***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        //cout << s << "  "<< p << endl;      
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        if(*p!='*'){
            if(*p==*s || *p== '?'){
                if(*s=='\0')
                    return false;
                return isMatch(s+1, p+1);
            }
            else
                return false;
        }
        while(*p == '*')
            ++p;
        if(*p=='\0')
            return true;
        while(*s!='\0'){
            if(isMatch(s, p))
                return true;
            s++;
        }
        while(*p)
            if(*p++ != '*')
                return false;
        return true;
    }
};

   /*******************************SOLUTION 2***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        int m=strlen(s), n=strlen(p);
        int nStar=0;
        for(int i=0; i<n; i++)
            if(p[i]=='*')
                nStar++;
        if(m<n-nStar)
            return false;
        
        vector<bool> helper(n+1, false);
        vector<vector<bool>> dp(2, vector<bool>(n+1, false));
        dp[0][0] = true;
        helper[0] = true;
        for(int i=1; i<=n && p[i-1]=='*'; i++){
            dp[0][i]=true;
            helper[i]=true;
        }

        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                dp[i%2][0] = false;  
                if(s[i-1]==p[j-1] || p[j-1]=='?')
                    dp[i%2][j]=dp[(i-1)%2][j-1];
                else if(p[j-1]=='*')
                    dp[i%2][j]=helper[j-1];
                else
                    dp[i%2][j]=false;
                if(dp[i%2][j])
                    helper[j]=true;
            }
        }

        return dp[m%2][n];
    }
};

   /*******************************SOLUTION 3***********************************/

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s==NULL || p==NULL)
            return false;
        if(*p=='\0')
            return *s=='\0';
        const char *pres=NULL, *prep=NULL;
        while(*s){
            if(*p==*s || *p=='?'){
                ++p;
                ++s;
                continue;
            }
            if(*p=='*'){
                while(*p == '*')
                    ++p;
                if(*p=='\0')
                    return true;
                pres = s;
                prep = p;
                continue;
            }
            if(prep!=NULL){
                p = prep;
                ++pres;
                s = pres;
                continue;
            }
            return false;
        }
        while(*p)
            if(*p++ != '*')
                return false;

        return true;
    }
};