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

原题如上

leetdcode给这道题打上的标记是有DP，虽然DP也能够做，但是我真的不认为DP是一个很直观的方法。好吧，我是普通青年，这题最难的地方在于backtracking，回溯，然而我卡在了这里。

对于匹配，一个很直观的方法就是贪心，尽可能的取匹配更多的字符。但是由于*这个字符可能匹配0个，1个或者多个，导致到底在匹配多少次上贪心算法并不能很好的控制。如果解决“*”这个字符的匹配难题呢？

我们还是以从头到尾的方式来匹配字符，对于‘*’的处理，我们是按照如下的：

1. If the next character of p is NOT ‘*’, then it must match the current character of s. Continue pattern matching with the next character of both s and p.

2. If the next character of p is ‘*’, then we do a brute force exhaustive matching of 0, 1, or more repeats of current character of p… Until we could not match any more characters.

如果下一个字符是'*'，那么我们应该对匹配0次，1次，多次做一次暴力求解，考虑所有的情况。每一种情况，以一个递归的方式去解决。

既然是递归，那么就要好好地考虑base。我认为这个递归的base应该是待匹配串和匹配串都已经扫描完。

int isMatch(char* s, char* p){    assert(s && p); //s and p are null    if (*p == '\0')    {        return *s == '\0';    }    if (*(p+1) != '*')  //next character is not '*'    {        assert(*p != '*');        if ((*p == *s) || (*p == '.' && *s != '\0'))        {            return isMatch(s+1, p+1);        }else{            return 0;        }    }else{ //next character is '*', match 0, 1, 2,... times        while ((*p == *s) || (*p == '.' && *s != '\0'))        {            if (isMatch(s, p+2))            {                return 1;            }            s++;        }        return isMatch(s, p+2);    }}