国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 《剑指offer》:[53]正则表达式匹配

《剑指offer》:[53]正则表达式匹配

来源:程序员人生   发布时间:2016-06-30 13:15:52 阅读次数:2199次
题目:请实现1个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意1个字符,而’‘表示它前面的字符可以出现任意次(包括0次)。在本题中,匹配是指字符串的所有字符匹配全部模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配。
   分析;常规中,如果是普通的两个字符串,那很简单,我们直接进行对照就能够了,这里又是要求匹配是指字符串的所有字符匹配全部模式,所以只要直接挨个比较就能够了,如果都相等则返回true;否则返回false;可是这个题目来了1个'.'和'*'两个比较烦人的东西,它改变了游戏的规则。把游戏变的复杂多变。
   首先要明确'.'肯定了字符的个数为1,并且为任意;'*'可以肯定它前面的字符的个数包括0次;
   第1种情况:当模式的第2个字符不是'*'的时候,如果字符串的第1个字符和模式串的第1个字符相等,则都向后移动1个,匹配剩下的字符串和模式串。如果不等则直接返回false;
    第2种情况:当模式的第2个字符是'*'的时候,这时候候就稍复杂点儿,由于这时候候存在不同的几种匹配方式:以字符串"aaa"与模式"ab*ac*a"匹配为例:
1、如果模式串中的字符和字符串中的字符不等如(a),且模式串的第2个字符为'*'。

      选择只有1种:在模式串上向后移动两个字符,疏忽掉b和*,由于'*'可以匹配0个字符;以下图:


2、如果模式串中的字符和字符串中的字符相等如(b),或模式串中为'.'如(c),并且模式串的第2个字符为'*'。其实(b)和(c)是1样的。这时候候选择有3种情况:
     (1)可以选择在模式串上向后移动两个字符,疏忽掉b和*,由于'*'可以匹配0个字符,字符串str保持不变;
     (2)可以选择超出'*','*'前的a当作有效的字符,且数量为1,str++;
     (3)可以选择模式串pattern不变,由于‘*’前的a可以任意数量的,并且和字符串str相等,只需要str++便可;

具体以下图所示:


具体实现代码以下:
#include <iostream> using namespace std; bool MatchCore(char *str,char *pattern) { if(*str=='\0' && *pattern=='\0') return true; if(*str!='\0' && *pattern=='\0') return false; if(*(pattern+1)=='*') { if(*pattern==*str || (*pattern=='.' && *str!='\0'))//将‘*’号疏忽,‘*’前的作为1个有效的值; return MatchCore(str+1,pattern+2) || MatchCore(str+1,pattern) //‘*’号前可以出现任意个,所以pattern可以保持不变 || MatchCore(str,pattern+2);//疏忽‘*’及‘*’号之前的字符; else return MatchCore(str,pattern+2);//由于‘*’ 号前的字符与*str不等,所以只能疏忽*pattern字符1个选择; } if(*str==*pattern || (*pattern=='.' && *str!='\0')) return MatchCore(str+1,pattern+1);//正常的字符串比较; return false; } bool match(char *str,char *pattern) { if(str==NULL || pattern==NULL) return false; return MatchCore(str,pattern); } int main() { char str[]="aaa"; char *pattern[4]={"a.a","ab*ac*a","aa.a","ab*a"}; for(int i=0;i<4;i++) { if(match(str,pattern[i])) cout<<"The same!"<<endl; else cout<<"Not the same!"<<endl; } system("pause"); return 0; }

运行结果:





生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生