剑指Offer(五十二):正则表达式匹配

  • A+
所属分类:剑指Offer
摘要

请实现一个函数用来匹配包括’.’和’*’的正则表达式。

剑指Offer(五十二):正则表达式匹配

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

这道题有些绕,需要好好思考下。

我们先来分析下如何匹配一个字符,现在只考虑字符'.',不考虑'*'看一下:

如果字符串和模式串的当前字符相等,那么我们继续匹配它们的下一个字符;如果模式串中的字符是'.',那么它可以匹配字符串中的任意字符,我们也可以继续匹配它们的下一个字符。

接下来,把字符'*'考虑进去,它可以匹配任意次的字符,当然出现0次也可以。

我们分两种情况来看:

  • 模式串的下一个字符不是'*',也就是上面说的只有字符'.'的情况。

如果字符串中的第一个字符和模式串中的第一个字符相匹配,那么字符串的模式串都向后移动一个字符,然后匹配剩余的字符串和模式串。如果字符串中的第一个字符和模式中的第一个字符不相匹配,则直接返回false。

  • 模式串的下一个字符是'*',此时就要复杂一些。

因为可能有多种不同的匹配方式。

选择一:无论字符串和模式串当前字符相不相等,我们都将模式串后移两个字符,相当于把模式串中的当前字符和'*'忽略掉,因为'*'可以匹配任意次的字符,所以出现0次也可以。

选择二:如果字符串和模式串当前字符相等,则字符串向后移动一个字符。而模式串此时有两个选择:

1、我们可以在模式串向后移动两个字符,继续匹配;

2、也可以保持模式串不变,这样相当于用字符'*'继续匹配字符串,也就是模式串中的字符'*'匹配字符串中的字符多个的情况。

用一张图表示如下:

剑指Offer(五十二):正则表达式匹配

如上图所示,当匹配进入状态2,并且字符串中的字符是'a'时,我们有两个选择:可以进入状态3(在模式串向后移动两个字符),也可以回到状态2(模式串保持不变)。

除此之外,还要注意对空指针的处理。

2、代码

C++:

Jack Cui
阿里云ECS

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: