本文共 1208 字，大约阅读时间需要 4 分钟。

题目描述

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

解题思路

这是一个字符串匹配的问题，只是有一些特殊字符的干扰，出现.可以代替任何字符，出现*则可以消去一些字符，我们只需要关注*，因为出现.我们可以认为匹配上了。

首先我们应从模式字符串里进行匹配，并看下一位是否含有*，如果有的话：

• 判断对应位置的字符是否相等，如果不相等，则模式字符串移动两位（消去），继续匹配
• 如果相等（出现.也算相等)，则可以消去模式字符，也可以不消去，继续递归向后匹配

如果没有的话两个字符串位置对照进行比较，如果不相等则匹配不成功（模式字符串里有.算做相等的情况）。

代码实现

class Solution {
   public:    bool match(char* str, char* pattern)    {
           if (str==NULL || pattern==NULL)return false;        return handle(str,pattern);    }    bool handle(char *str,char *pattern){
           if(*str=='\0' && *pattern=='\0')return true;        if(*str!='\0' && *pattern=='\0')return false;        if(*(pattern+1)=='*'){
               if(*str==*pattern||(*pattern=='.' && *str!='\0'))                return handle(str+1,pattern+2)||//b前面出现1次                handle(str+1,pattern)||//b前面出现n次                handle(str,pattern+2);//抹去前面，就算匹配了也不计数            else                return handle(str,pattern+2);//不相等，但后一位出现了‘*’，可消去        }        if(*str==*pattern||(*pattern=='.'&&*str!='\0'))            return handle(str+1,pattern+1);        return false;    }};

运行时间：2ms占用内存：472k

转载地址：https://blog.csdn.net/Jeaten/article/details/108303947 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！