LeetCode: 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

---

Since '*' matches any sequence of characters, we need to check every possibility within string s. Instead of using recursion, we can use iteration with two variables recording position of last '*' in pattern string and corresponding position in string s.

C++ Code:

/*
 * func: wildcard_match
 * goal: wildcard pattern match with support for '?' and '*'
 * @param s: string to be checked
 * @param p: pattern to be used
 * return: true or false
 */
bool wildcard_match(const char* s, const char* p){
    if(! *s && ! *p){
        return true;
    }
    char* start_s = nullptr;
    char* start_p = nullptr;
    
    while(*s != '\0'){
        if(*p == *s || *p == '?'){
            ++p;
            ++s;
        }else if(*p == '*'){
            //skip continuous '*'
            while(*p == '*'){
                ++p;
            }
            //If '*' is the last letter, return true
            if(*p == '\0'){
                return true;
            }
            
            start_p = const_cast<char*>(p);
            start_s = const_cast<char*>(s);
        }else if((*p != '\0' || *p != *s) && start_p != nullptr){
            //If current char is not matched, include it to the * and backtrace
            s = ++start_s;
            p = start_p;
        }else{
            return false;
        }
    }
    
    //Check if remaining part of pattern is all of '*'
    while(*p != '\0'){
        if(*p++ != '*'){
            return false;
        }
    }
    
    return true;
}

Python Code:

# func: wildcard pattern match with support for '?' and '*'
# @param s: an input string
# @param p: a pattern string
# @return: True or False
def wildcard_match(s, p):
    s_index = 0
    p_index = 0
    star = -1
    while s_index < len(s) and p_index <= len(p):
        if p_index != len(p):
            if p[p_index] == '?' or p[p_index] == s[s_index]:
                s_index += 1
                p_index += 1
                continue
            if p[p_index] == '*':
                star = p_index
                p_index += 1
                #Record the current index of s when a '*' occur in p
                s_star = s_index
                continue
        if star != -1:
            p_index = star + 1
            s_index = s_star + 1
            s_star += 1
            continue
        return False
    #Remove '*' in the remaining part
    while p_index < len(p) and p[p_index] == '*':
        p_index += 1

    if p_index == len(p):
        if s_index == len(s):
            return True
        else:
            return False
    else:
        return False

Reference Link:

[closed] Wildcard Matching - LeetCode http://discuss.leetcode.com/questions/222/wildcard-matching