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

前端之家收集整理的这篇文章主要介绍了《剑指offer》:[53]正则表达式匹配前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
题目:请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符,而’‘表示它前面的字符可以出现任意次(包含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串”aaa”与模式”a.a”和”ab*ac*a”匹配,但是与”aa.a”和”ab*a”均不匹配。
分析;常规中,如果是普通的两个字符串,那很简单,我们直接进行对比就可以了,这里又是要求匹配是指字符串的所有字符匹配整个模式,所以只要直接挨个比较就可以了,如果都相等则返回true;否则返回false;可是这个题目来了一个'.'和'*'两个比较烦人的东西,它改变了游戏的规则。把游戏变的复杂多变。
首先要明确'.'确定了字符的个数为1,并且为任意;'*'可以确定它前面的字符的个数包括0次;
第一种情况:当模式的第二个字符不是'*'的时候,如果字符串的第一个字符和模式串的第一个字符相等,则都向后移动一个,匹配剩下的字符串和模式串。如果不等则直接返回false;
第二种情况:当模式的第二个字符是'*'的时候,这时候就稍复杂点儿,因为这时候存在不同的几种匹配方式:以字符串"aaa"与模式"ab*ac*a"匹配为例:
1、如果模式串中的字符和字符串中的字符不等如(a),且模式串的第二个字符为'*'。

选择只有一种:在模式串上向后移动两个字符,忽略掉b和*,因为'*'可以匹配0个字符;如下图:


2、如果模式串中的字符和字符串中的字符相等如(b),或者模式串中为'.'如(c),并且模式串的第二个字符为'*'。其实(b)和(c)是一样的。这时候选择有三种情况:
(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'))//将‘*’号忽略,‘*’前的作为一个有效的值;
			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!='\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;
}

运行结果:

原文链接:https://www.f2er.com/regex/359131.html

猜你在找的正则表达式相关文章