《剑指offer》:[53]正则表达式匹配
发布时间：2020-12-14 04:22:24 所属栏目：百科 来源：网络整理
导读：题目：请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配
|
题目：请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配。
分析；常规中，如果是普通的两个字符串，那很简单，我们直接进行对比就可以了，这里又是要求匹配是指字符串的所有字符匹配整个模式，所以只要直接挨个比较就可以了，如果都相等则返回true；否则返回false；可是这个题目来了一个'.'和'*'两个比较烦人的东西，它改变了游戏的规则。把游戏变的复杂多变。 首先要明确'.'确定了字符的个数为1，并且为任意；'*'可以确定它前面的字符的个数包括0次； 第一种情况：当模式的第二个字符不是'*'的时候，如果字符串的第一个字符和模式串的第一个字符相等，则都向后移动一个，匹配剩下的字符串和模式串。如果不等则直接返回false； 第二种情况：当模式的第二个字符是'*'的时候，这时候就稍复杂点儿，因为这时候存在不同的几种匹配方式：以字符串"aaa"与模式"ab*ac*a"匹配为例： 1、如果模式串中的字符和字符串中的字符不等如(a)，且模式串的第二个字符为'*'。 选择只有一种：在模式串上向后移动两个字符,忽略掉b和*，因为'*'可以匹配0个字符；如下图：
（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==' ' && *pattern==' ')
return true;
if(*str!=' ' && *pattern==' ')
return false;
if(*(pattern+1)=='*')
{
if(*pattern==*str || (*pattern=='.' && *str!=' '))//将‘*’号忽略，‘*’前的作为一个有效的值；
return MatchCore(str+1,pattern+2)
|| MatchCore(str+1,pattern) //‘*’号前可以出现任意个，所以pattern可以保持不变
|| MatchCore(str,pattern+2);//忽略‘*’及‘*’号以前的字符；
else
return MatchCore(str,pattern+2);//因为‘*’ 号前的字符与*str不等，所以只能忽略*pattern字符一个选择；
}
if(*str==*pattern || (*pattern=='.' && *str!=' '))
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;
}
运行结果：
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |