请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

思路：

由于'.'可以表示任何字符，所以这个无论匹配到何种非结束标志字符都算匹配成功。但'*'就不一样了，它得考虑次数：0次或多次。所以我们更多的是考虑星号。

  1. 若字符串str与模式字符串pattern为空时，返回false;

  2. 两种特殊情况：若str与pattern都为空字符串，匹配成功，返回true; 若str不为空字符串但pattern为空字符串时，返回false;

  3. 当模式串中第二个字符是‘ * ’时，问题要复杂一些，因为有很多种可能的匹配方式。
    3.1 形如aaa与ab*aa,这种就相当于星号和他前面的字符被忽略了，则str向后移动一位，pattern向后移动两位；
    3.2 形如abbbaa与ab *aa，这种星号就表示前面的字符超过了一位，则str向后移一位,pattern不变；
    3.3 形如aaa与a *aa，忽略一个星号，则str向后移一位，pattern向后移两位。

  4. 当模式串中第二个字符不是‘ * ’时，问题就简单很多，直接一一匹配即可。
    代码：

    bool match(char* str, char* pattern)
 {
     if (str == nullptr && pattern == nullptr)
         return false;
     else
         return matchCore(str, pattern);
 }

 bool matchCore(char* str, char* pattern)
 {
     if (*str == '\0' && *pattern == '\0')
         return true;
     if (*str != '\0' && *pattern == '\0')
         return false;

     if (*(pattern + 1) == '*')
     {
         if (*str == *pattern || (*pattern == '.' && *str != '\0'))
             return matchCore(str + 1, pattern) || matchCore(str, pattern + 2) || matchCore(str + 1, pattern + 1);
         else
             return matchCore(str, pattern + 2);
     }

     else
     {
         if (*str == *pattern || (*pattern == '.' && *str != '\0'))
             return matchCore(str + 1, pattern + 1);
         else
             return false;
     }
 }

FRESH....

思路是一样滴：

/*
    解这题需要把题意仔细研究清楚，反正我试了好多次才明白的。
    首先，考虑特殊情况：
         1>两个字符串都为空，返回true
         2>当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法
            匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成
            功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，
            所以有可能匹配成功）
    之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern
    下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或
    不为‘*’：
          1>pattern下一个字符不为‘*’：这种情况比较简单，直接匹配当前字符。如果
            匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的
            “匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的
            当前字符为‘.’,同时str的当前字符不为‘\0’。
          2>pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。
            这里把这些情况都考虑到：
               a>当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，
                跳过这个‘*’符号；
               b>当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符
                不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，
                由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；
                当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
    之后再写代码就很简单了。
*/
class Solution {
public:
    bool match(const char* s, const char* p)
    {
        if (s == nullptr || p == nullptr)
            return false;
        return matchCore(s, p);
    }

    bool matchCore(const char* s, const char* p)
    {
        //递归结束标志
        if (*s == '\0' && *p == '\0')
            return true;
        if (*s != '\0' && *p == '\0')
            return false;

        //当p后一位不为*时，不用跳过匹配，一步步匹配即可。
        if (*(p + 1) != '*')
        {
            if (*p == *s || (*p == '.' && *s != '\0'))
            {
                return matchCore(s + 1, p + 1);
            }
            else
                return false;
        }
        //当p后一位为*时，考虑匹配的多种情况
        else
        {
            /*当'*'匹配到1个或多个字符时，s向后移动一个，p保持不变。
            移动到最后可能s已经移动到下一个不匹配的字符，此时s不动,p向后移动两位跳过'*'
            */
            if (*p == *s || (*p == '.'&&*s!='\0'))
            {
                return matchCore(s, p + 2)||matchCore(s + 1, p);
            }    
            //当匹配0个字符时，s字符不变，p向后移两位跳过这个‘*’符号
            else
            {
                return matchCore(s, p + 2);
            }
        }
    }
};