剑指offer 53正则表达式匹配

题目描述

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

链接：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c来源：牛客网class Solution {public:    bool match(char* str, char* pattern)    {        //1.有效性检查        /*          str不能有.*         pattern模式中*前面必须有一个字符        */          //2.匹配情况         /*定义s[i]和p[i]表示从i位置到结尾的字符串            1)  s[i],p[i]不相等时，而且P[i+1]！=*或者.,则return false                                 如果P[i+1]=*则s[i]与p[i+2]继续比较            2) s[i],p[i]相等时,如果p[i+1]=*,比如s=xxxxzzzz,p=x*yyyy                                如果p[i+1]不等于*时，则i++        */      if(str==NULL||pattern==NULL)      {          return false;      }      for(int i=0;i<(int)strlen(str);i++)      {          if(str[i]=='.'||str[i]=='*')          {              return false;          }      }        for(int i=0;i<(int)strlen(pattern);i++)        {            if(pattern[i]=='*'&&(i==0||pattern[i-1]=='*'))            {                return false;            }        }      return  expMatch(str,0,pattern,0);    }         bool expMatch(char* s,int si,char* p,int pi)    {       if(pi==(int)strlen(p))       {           return si==(int)strlen(s);       }        //注意p只有两个字符而且没有*时,要求满足p[i]==s[i]而且si不能为最后一个字符       if(pi+1==(int)strlen(p)||p[pi+1]!='*')       {          return si!=(int)strlen(s)&&(s[si]==p[pi]||p[pi]=='.')              &&expMatch(s,si+1,p,pi+1);       }       /*       p[i+1]=*,s[i],p[i]相等时,比如s=xxxxzzzz,p=x*yyyy       */        while(si!=(int)strlen(s)&&(s[si]==p[pi]||p[pi]=='.'))        {            if(expMatch(s,si,p,pi+2))            {                return true;            }            si++;        }       return expMatch(s,si,p,pi+2);    }};

#include<regex>class Solution {public:bool match(char* str, char* pattern){        if(str[0]=='\0'&&pattern[0]=='\0')//如果二者为空则返回true            return true;        else if(str[0]!='\0'&&pattern[0]=='\0')            return false;//如果字符串不为空，而模式串为空，返回false;        	//当第二个字符不为‘*’时：匹配就是将字符串和模式的指针都下移一个，不匹配就直接返回false        if(pattern[1]!='*'){            if(str[0]==pattern[0]||(pattern[0]=='.'&&str[0]!='\0'))                return match(str+1,pattern+1);            else                return false;        }        else{//当第二个字符为'*'时：                        if(str[0]==pattern[0]||(pattern[0]=='.'&&str[0]!='\0'))                return match(str,pattern+2)||match(str+1,pattern)||match(str+1,pattern+2);             else                return match(str,pattern+2);//不匹配：字符串下移不动，模式下移两个        }    /*		   匹配：                a.字符串下移一个，模式不动                b.字符串下移一个，模式下移两个                c.字符串不动，模式下移两个        不匹配：字符串下移不动，模式下移两个    */            } };