正则表达式匹配

1、题目

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

2、解题1

按照是否相等进行判断分类

class Solution { public: bool match(char* str, char* pattern) { if(str == NULL || pattern == NULL)return false; char one = '\0'; bool flag = JudgeMatch(str,pattern,one,0); return flag; } bool JudgeMatch(char* str,char* pattern,char one,int pos){ if(pos < 0)return false; if(*str == '\0' && *pattern == '\0')return true; if(*pattern == '\0')return false; if(*str == '\0'){ //不回退的情况 bool flag = true; bool has = false; if(*pattern != '*'){ pattern++; }else{ has = true; } if(*pattern != '*')flag = false; while(*pattern != '\0' && *pattern == '*')pattern++; if(*pattern != '\0'){ if(flag == true){ flag = false; } } if(flag == true)return true; if(has == false)return false; //回退的情况 char tmp = '\0'; return JudgeMatch(str-1,pattern,tmp,pos-1); } //不等情况 if(*pattern != *str){ //都是字母的情况 if(*pattern != '.' && *pattern != '*'){ char *tmpLast = pattern+1; //后面没有*情况 if(*tmpLast != '*')return false; char tmp = '\0'; return JudgeMatch(str,tmpLast+1,tmp,pos); } if(*pattern == '.'){ char tmp = *pattern; return JudgeMatch(str+1,pattern+1,tmp,pos+1); } //处理pattern带*的情况,不等的情况 if(one != '.' && one != *str){ char tmp = '\0'; return JudgeMatch(str,pattern+1,tmp,pos); } //处理相等的情况 //1,*代表多个字符 bool flag = JudgeMatch(str+1,pattern,one,pos); //2，*代表1个字符 if(flag == false){ char tmp = '\0'; char *tmpPattern = pattern; while(*tmpPattern != '\0' && *tmpPattern == '*')tmpPattern++; flag = JudgeMatch(str,tmpPattern,tmp,pos); } //3，*代表0个字符 if(flag == false){ char tmp = '\0'; char *tmpPattern = pattern; while(*tmpPattern != '\0' && *tmpPattern == '*')tmpPattern++; flag = JudgeMatch(str-1,tmpPattern,tmp,pos-1); } return flag; }else{ //相等的情况 char tmp = *pattern; return JudgeMatch(str+1,pattern+1,tmp,pos+1); } } };

3、解题2（简化）

按照是否有*进行判断分类

class Solution { public: bool match(char* str, char* pattern) { if(str == NULL || pattern == NULL)return false; bool flag = JudgeMatch(str,pattern); return flag; } bool JudgeMatch(char* str,char* pattern){ if(*str == '\0' && *pattern == '\0')return true; if(*pattern == '\0')return false; if(*(pattern+1) == '*'){ if(*pattern == *str || (*str != '\0' && *pattern == '.')){ return JudgeMatch(str+1,pattern) || JudgeMatch(str,pattern+2);; }else{ return JudgeMatch(str,pattern+2); } }else{ //相等的情况 if(*pattern == *str || (*str != '\0' && *pattern == '.')){ return JudgeMatch(str+1,pattern+1); }else{ //不等的情况 return false; } } } };