44 Wildcard Matching

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 of my own!

class Solution {
public:
    bool isMatch(string s, string p) {
        int ns = s.size(), np = p.size();
        int is = 0, ip = 0;
        int back_s = -1, back_p = -1;
        while ( is <= ns-1 ) {
            // matching case
            if ( ip <= np-1 and (s[is] == p[ip] or p[ip] == '?' )) {
                is += 1; ip += 1;
                continue;
            }
            // special case of '*'
            if ( ip <= np-1 and p[ip] == '*' ) {
                back_s = is;
                back_p = ++ip;
                continue;
            }
            // all the rest cases
            if ( back_s == -1 ) return false;
            is = ++back_s;
            ip = back_p;
        }
        while ( ip <= np-1 ) {
            if ( p[ip++] != '*' ) return false;
        }
        return true;
    }
};

Notes
When something fails, always go back to the last comparing '*' in p and corresponding position in s. Note only the last position of '*' matters here. (unlike regular expression matching.)

• Matching case, simply continue;
• Special case of '*', record the position to go back:

  back_s = is;
  back_p = ++ip;
  

• Something goes wrong, go back to the last position recorded:

  is = ++back_s;
  ip = back_p
  

Solution from others!

class Solution(object):
    def helper(self, s, p, i, j):
        sol = Solution()
        ns = len(s)
        np = len(p)
        i, j = 0, 0
        i0, j0 = 0, 0
        tag = False
        while ( i <= ns-1 ):
            if ( j == np or ( p[j] != '*' and p[j] != '?' and s[i] != p[j] )):
                if ( not tag ): return False
                i0 += 1
                i, j = i0, j0
                continue
            if ( p[j] == '?' ):
                i += 1
                j += 1
                continue
            if ( p[j] == '*' ):
                tag = True
                i0, j0 = i, j
                while ( p[j0] == '*' ):
                    j0 += 1
                    if ( j0 == np ): return True
                i, j = i0, j0
                continue
            if ( s[i] == p[j] ):
                i += 1
                j += 1
                continue
        if ( j == np ): return True
        while ( p[j] == '*' ):
            j += 1
            if ( j == np ): return True
        return False
    def isMatch(self, s, p):
        sol = Solution()
        return sol.helper(s, p, 0, 0)