这道题最初刷题连答案都看不懂，实在不是一道容易的题目。

补充两个C++知识：

1）string对象的.c_str() 返回一个c语言字符串指针 即const char* p类型的指针；

2）c语言字符串的末尾为‘\0’可以用  *p==0  判断是否到达末尾。

 

递归解法不断的对当前情况和之后的情况进行判断：

1）当前匹配字符串p为空，如果此时s为空则return true,s不为空则return false;

2）当前匹配字符串p不为空，那么对当前p和s进行匹配（不考虑下一位是否有*），结果为match

 　　2.1）下一位有*时，a和b都有可能有正确的解：

　　　　a)如果正解在a中，即当前字符串应该出现0次，那么无论当前的match成功与否，return isMatch(s,p.substr(2));

　　　　b)如果正解再b中，即当前字符串至少出现1次，那么当前至少应该匹配成功，并且还要递归求解isMatch(s.substr(1),p.substr(1))，即return match&&isMatch(s.substr(1),p.substr(2));

　　2.2 ) 下一位没有*时，

　　　　a)如果当前匹配成功match==true，那么匹配下一个字符，即 if(match) return isMatch(s.substr(1),p.substr(2));

　　　　b)如果当前匹配失败match==false，那么不用匹配直接return false;

 

C++ 代码如下：

一）使用string对象不使用指针

class Solution {public:    bool isMatch(string s, string p) {        //情况1，加入p为空那么只要s为空那么得到true反之false        if(p.empty()) return s.empty();        //计算当前对应字符的匹配first_match,p不为空，匹配当前第一个字符（不包含s为空而p为a*之类的情况，只探讨是否字母直接匹配和.匹配）        bool match=!s.empty()&&(s[0]==p[0] || p[0]=='.');                //情况2，p当前长度大于2，而且下一个字符是*（p.length()>=2 && p[1]=='*'）        if(p.length()>=2 && p[1]=='*'){        // 2.1（*为0个的情况）当前对应位置字符不匹配即first_match==false，那么p当前字母为0个时还有匹配可能,即s和p.substr(2)            //或者当前字符能匹配first_match=true但不合适因此也需要为0个，即s和p.substr(2)        // 2.2（*为1个以上的情况）当前对应字符匹配 first_match==true,而且正确答案就在此，那么匹配s的下一个字符和当前p的字符（因为*代表任意多的情况            return isMatch(s,p.substr(2)) || match && isMatch(s.substr(1),p);        }else{        //情况3，如果p只剩下1个,而这时        // 3.1 first_match==true,那么去决议s.substr(1)和p.substr(1)        // 3.2 first_match==false,那么已经false，不用继续了            if(match)                return isMatch(s.substr(1),p.substr(1));            else                return false;        }    }};

缺点：递归过程中，需要不断的复制储存子串，因此时间消耗较多，几百ms

 

二）使用指针：

// 优化后递归的版本，通过传递指针省去不断的复制和存储 20msclass Solution {public:    bool isMatch(string s, string p) {        //string对象的.c_str()返回一个c字符串的指针，即const char *        return isMatch(s.c_str(),p.c_str());    }    bool isMatch(const char* s,const char* p){        //c字符串是以\0结尾的        if(*p==0) return *s==0;                bool match=(*s!=0) && (*s==*p||*p=='.');                if(*(p+1)=='*'){            return isMatch(s,p+2)|| match&&isMatch(s+1,p);        }else{            return match&&isMatch(s+1,p+1);        }    }};

缺点：使用指针，相对更容易出bug和难以理解