這道題最初刷題連答案都看不懂，實(shí)在不是一道容易的題目。

補(bǔ)充兩個C 知識：

1）string對象的.c_str() 返回一個c語言字符串指針 即const char* p類型的指針；

2）c語言字符串的末尾為‘\0’可以用? *p==0? 判斷是否到達(dá)末尾。

?

遞歸解法不斷的對當(dāng)前情況和之后的情況進(jìn)行判斷：

1）當(dāng)前匹配字符串p為空，如果此時s為空則return true,s不為空則return false;

2）當(dāng)前匹配字符串p不為空，那么對當(dāng)前p和s進(jìn)行匹配（不考慮下一位是否有*），結(jié)果為match

?　　2.1）下一位有*時，a和b都有可能有正確的解：

　　　　a)如果正解在a中，即當(dāng)前字符串應(yīng)該出現(xiàn)0次，那么無論當(dāng)前的match成功與否，return isMatch(s,p.substr(2));

　　　　b)如果正解再b中，即當(dāng)前字符串至少出現(xiàn)1次，那么當(dāng)前至少應(yīng)該匹配成功，并且還要遞歸求解isMatch(s.substr(1),p.substr(1))，即return match&&isMatch(s.substr(1),p.substr(2));

　　2.2 ) 下一位沒有*時，

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

　　　　b)如果當(dāng)前匹配失敗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();
        //計(jì)算當(dāng)前對應(yīng)字符的匹配first_match,p不為空，匹配當(dāng)前第一個字符（不包含s為空而p為a*之類的情況，只探討是否字母直接匹配和.匹配）
        bool match=!s.empty()&&(s[0]==p[0] || p[0]=='.');
        
        //情況2，p當(dāng)前長度大于2，而且下一個字符是*（p.length()>=2 && p[1]=='*'）
        if(p.length()>=2 && p[1]=='*'){
        // 2.1（*為0個的情況）當(dāng)前對應(yīng)位置字符不匹配即first_match==false，那么p當(dāng)前字母為0個時還有匹配可能,即s和p.substr(2)
            //或者當(dāng)前字符能匹配first_match=true但不合適因此也需要為0個，即s和p.substr(2)
        // 2.2（*為1個以上的情況）當(dāng)前對應(yīng)字符匹配 first_match==true,而且正確答案就在此，那么匹配s的下一個字符和當(dāng)前p的字符（因?yàn)?代表任意多的情況
            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,那么已經(jīng)false，不用繼續(xù)了
            if(match)
                return isMatch(s.substr(1),p.substr(1));
            else
                return false;
        }
    }
};

缺點(diǎn)：遞歸過程中，需要不斷的復(fù)制儲存子串，因此時間消耗較多，幾百ms

?

二）使用指針：

// 優(yōu)化后遞歸的版本，通過傳遞指針省去不斷的復(fù)制和存儲 20ms
class 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結(jié)尾的
        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);
        }
    }
};

缺點(diǎn)：使用指針，相對更容易出bug和難以理解

?