leetcode-Regular Expression Matching

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

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","a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true

It seems that some readers are confused about why the regex pattern".*"matches the string"ab".".*"means repeat theprecedingelement 0 or more times. Here,the"preceding"element is thedotcharacter in thepattern,which can match any characters. Therefore,the regex pattern".*"allows the dot to be repeated any number of times,which matches any string (even an empty string). Think carefully how you would do matching of'*'.Please note that'*'in regular expression isdifferentfrom wildcard matching,as we match the previous character 0 or more times. But,how many times? If you are stuck,recursion is your friend.

bool isMatch(const char *s,const char *p) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if (*p == 0) return *s == 0;
        if (*(p+1) != '*')
        {
            if (*s != 0 && (*p == *s || *p == '.')) return isMatch(s+1,p+1);
            else return false;
        }
        else
        {
            // *s == *p
            while (*s != 0 && (*s == *p || *p == '.'))
            {
                if (isMatch(s,p+2)) return true;
                s++;
            }
            return (isMatch(s,p+2));
        }
    }

bool isMatch(const char *s,const char *p) {
    assert(s && p);
    if (*p == '') return *s == '';

    // next char is not '*': must match current character
    if (*(p+1) != '*') {
        assert(*p != '*');
        return ((*p == *s) || (*p == '.' && *s != '')) && isMatch(s+1,p+1);
    }
	
    // next char is '*'
    while ((*p == *s) || (*p == '.' && *s != '')) {
        if (isMatch(s,p+2)) return true;
        s++;
    }
    return isMatch(s,p+2);
}

Solution:
This looks just like a straight forward string matching,isn't it? Couldn't we just match the pattern and the input string character by character? The question is,how to match a'*'?

A natural way is to use a greedy approach; that is,we attempt to match the previous character as many as we can. Does this work? Let us look at some examples.

s="abbbc",p="ab*c"Assume we have matched the first'a'on bothsandp. When we see"b*"inp,we skip all b's ins. Since the last'c'matches on both side,they both match.

s="ac",238)">"ab*c"After the first'a',we see that there is no b's to skip for"b*". We match the last'c'on both side and conclude that they both match.

It seems that being greedy is good. But how about this case?

s="abbc",238)">"ab*bbc"When we seeOne might be tempted to think of a quick workaround. How about counting the number of consecutive b's ins? If it is smaller or equal to the number of consecutive b's afterThis seem to solve the above problem,but how about this case:s="abcbcd",238)">"a.*c.*d"