正则表达式匹配
发布时间
阅读量：
阅读量
文章目录
- 题目和C++代码
- 算法思想
- 牛客网链接
题目和C++代码
/*请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配*/
bool match(char* str, char* pattern)
{
char *a=str;
char *b=pattern;
int len_a=strlen(a);
int len_b=strlen(b);
if(lenb==0) return len_a==0; //如果模式已经结束，str未结束肯定匹配失败
bool flag=len_a>0&&(b[0]=='.'||(a[0]==b[0])); //判断a[0]和b[0]是否相等和str结束没
if(len_b>1&&b[1]=='*'){ //patter[1]=*,落入第二种大情况
return match(a,b+2)||(flag&&match(a+1,b)); //flag为0，则a+1不存在或a[0]不等于b[0]
//则只存在第二种大情况的第一种小情况或者第二种大情况的第二种小情况的1号情况
//flag=1，则存在第二种大情况的第二种小情况的1,2号情况，但是此时的1等于上面的1，不用重复写
}else{
return flag&&match(a+1,b+1); //pattern[1]不为*，落入第一种大情况
}算法思想
深入分析*号的特性及其影响。随后采用点符号（•）来替代星号。在这种情况下，在pattern数组中第一个元素（pattern[1]）与星号并不相等。
如果现在str指针的第一个字符不等于pattern的第一个字符，那么要让模式能匹配，patter，后面必然要跟一个星号即pattern[1]=星号，能让str[0]跳过pattern[0]跟pattern[2]继续比较。所以，若pattern[1]不为星号，即patter[0]必然存在于模式，那么str[0]就不能等于模式集合的第一个字符。所以直接返回False。
如果str[0]=pattern[0]，那么str和pattern都移向下一个字符。str[0]=str[1],pattern[0]=pattern[1]。
第二种大情况:当前pattern[1]=星号。
举例说明...
由于每次下一种情况的处理的判断都是相同的，所以是递归判断。
牛客网链接
全部评论 (0)
还没有任何评论哟~