正则表达式匹配_正则表达式匹配字符串长度

全栈程序员-站长 • 2022年8月2日上午6:00 • 未分类 • 阅读 8

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

题目描述

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

提交链接：
点击

思路：
分两种情况讨论

　　
1.第2个字符不为*时

　　　　1.1 当前主串字符和模式串字符匹配，那么主串和模式串指针相应往后移一位，接着递归进行匹配

　　　　　　
(匹配有两种情况，一种是直接相等；另一种是模式串为.且主串不为空)

　　　　1.2 当前主串字符和模式串字符不匹配，那么直接返回false

　　2.第2个字符为*时

　　　　2.1 当前主串字符和模式串字符匹配，那么分为三种情况：

　　　　　　2.1.1 *取值为0，主串指针不动，模式串指针+2

　　　　　　2.1.2 *取值为1，主串指针+1，模式串指针+2

　　　　　　2.1.3 *取值为多，主串指针+1，模式串指针不动

　　　　　　（其中2.1.2可由先2.1.3再2.1.1得到，因此下面代码红色阴影部分可不写，提升算法速度！）

　　　　2.2 当前主串字符和模式串字符不匹配，那么就是*直接取值为0，模式串指针+2跟接下来的字符进行匹配，表示跳过此字符。

代码：

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(str[0]=='\0' && pattern[0]=='\0'){
            return true;
        }else if(str[0]!='\0' && pattern[0] =='\0'){
            return false;
        } 
        if(pattern[1]!='*'){  //第2个字符不为*
            if(str[0]==pattern[0]||(pattern[0]=='.' && str[0]!='\0')){ //字符匹配
                return match(str+1,pattern+1);
            }else{ //字符不匹配
                return false;
            }
        }else{  //第2个字符为*
            if(str[0]==pattern[0]||(pattern[0]=='.' && str[0]!='\0')) //字符匹配
                return match(str,pattern+2) || match(str+1,pattern+2) || match(str+1,pattern);
            else
                return match(str,pattern+2);  //字符不匹配
        }
    }
};