1.题目描述

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

2.解法分析

递归解就好了

class Solution {
        public: bool isMatch(const char *s, const char *p) {
        // Start typing your C/C++ solution below // DO NOT write int main() function if(s==NULL&&p==NULL)return true; else if(s==NULL||p==NULL)return false; return __isMatch(s,p,0,0);     } bool __isMatch(const char *s, const char *p ,int sFront, int pFront)     {
        if(s[sFront]=='\0'&&p[pFront]=='\0')return true; else if(p[pFront]=='\0')return false; if(s[sFront]=='\0')             {
        if(p[pFront+1]=='*') return __isMatch(s,p,sFront, pFront+2); else return false;             } //模式串首字符字符为普通字符 if(p[pFront]!='.'&&p[pFront]!='*')         {
        //模式串第二个字符不是‘*’,需严格匹配 if(p[pFront+1]!='*')             {
        if(p[pFront]==s[sFront])return __isMatch(s,p,sFront+1,pFront+1); else return false;             } else//模式串第二个字符为'*'             {
        //若源串第一个字符与模式串第一个字符相同，则考虑是否匹配源串这个字符，若不相同，源串首字符不匹配 if(p[pFront]==s[sFront])return __isMatch(s,p,sFront,pFront+2)||__isMatch(s,p,sFront+1,pFront); else return __isMatch(s,p,sFront,pFront+2);             }         } //模式串首字符为'.'的分析大体同模式串首字符为普通字符的情况 if(p[pFront]=='.')         {
        if(p[pFront+1]!='*')             {
        return __isMatch(s,p,sFront+1,pFront+1);             } else             {
        return __isMatch(s,p,sFront,pFront+2)||__isMatch(s,p,sFront+1,pFront);             }         } if(p[pFront]=='*')return false;//正常情况*字符不会裸露     } };