Leetcode---Regular Expression Matching

Implement regular expression matching with support for '.' and '*'.

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

Have you been asked this question in an interview?

先解释一下例子中的

isMatch("ab", ".*") → true

刚开始看题的时候没有理解为啥这个是true~~~，后来看了一篇老外的文章明白了，”.*“指的是0到多个"."的组合。。。

好的言归正传，我得说这道题做的很痛苦，why？很难简练的总结出递归的规律。
最后参考了网上的一些思路，好好整理了一下，得出以下结论：
1. 当没有*时，匹配很简单，问题等同于 (*s==*p || *p=='.') && isMatch(s+1,p+1)
2. 当有*时，就有很多种匹配可能，例如
“a*”的匹配可能是
“”，“a”，“aa”，“aaa”... ，"aaaaaaaaaa..."
这许多可能中只要有一个最终匹配成功了，整个字符串就算匹配成功了。

所以最终思路为
1. return所有可能匹配成功的情况，剩下的就是匹配不成功的情况
2. 处理*字符，把*字符当做 “0到n个*之前的字符” 来处理

code如下，单步调了好久！！！

bool isMatch(const char *s, const char *p){
    if(*s=='\0' && *p=='\0')
        return true;
    else if(*s!='\0' && *p=='\0')
        return false;
    else if(*s=='\0' && *(p+1)!='*')
        return false;
    if(*(p+1)!='*')
        return (*s==*p || *p=='.') && isMatch(s+1,p+1);
    else{
        while((*s==*p || *p=='.') && *s!='\0'){
            if(isMatch(s,p+2))
                return true;
            s++;
        }
        return isMatch(s,p+2);
    }
    return false;
}