专栏首页用户画像剑指offer 正则表达式匹配

剑指offer 正则表达式匹配

版权声明:本文为博主-姜兴琪原创文章,未经博主允许不得转载。

题目描述

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

分析:递归实现

每次分别在str 和pattern中取一个字符进行匹配,如果匹配,则匹配下一个字符,否则,返回不匹配。

设匹配递归函数 match(str, pattern)。

如果模式匹配字符的下一个字符是‘*’:

•如果pttern当前字符和str的当前字符匹配,:有以下可能情况

(1)pttern当前字符能匹配 str 中的 0 个字符:match(str, pattern+2)

(2)pttern当前字符能匹配 str 中的 当前 字符:match(str+1, pattern)

•如果pttern当前字符和和str的当前字符不匹配

pttern当前字符能匹配 str 中的 0 个字符:(str, pattern+2)

如果模式匹配字符的下一个字符不是‘*’,进行逐字符匹配。

对于 ‘.’ 的情况比较简单,’.’ 和一个字符匹配 match(str+1, pattern+1)

另外需要注意的是:空字符串”” 和 “.*” 是匹配的

class Solution {
public:
    bool match(char* str, char* pattern)
    {
        if(*str=='\0')
        {
            if(*pattern=='\0'||(*(pattern+1)=='*'&&*(pattern+2)=='\0')) //空串和“b*”是匹配的
                return true;
            else return false;
        }
        if(*pattern=='\0')
            return false;
        if(*(pattern+1)=='*'){
            if(*pattern==*str||*pattern=='.')
                return match(str+1,pattern)||match(str,pattern+2); 
            //两种情况,一种是出现次数大于0,那就是str+1,pattern不变;另一种是出现次数等于0
            else return match(str,pattern+2);//不符合要求,当做出现次数为0
        }
        if(*pattern==*str||*pattern=='.')
            return match(str+1,pattern+1);
        return false;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 正则表达式匹配 整数和正整数

    ?匹配前面的子表达式零次或一次,或指明一个非贪婪限定符。要匹配 ? 字符,请使用 \?

    week
  • 2.2.2 物理层接口的特性

    物理层考虑的是如何在连接各个计算机的传输媒体上传输数据比特流,而不是具体的传输媒体。物理层应尽可能屏蔽各种物理设备的差异,使数据链路层只需考虑本层的协议和服务。...

    week
  • 第21章 DHCP

    1.在TCP/IP协议族中,应用层的各种服务是建立在传输层提供服务的基础上,下列哪组协议需要使用传输层的TCP建立连接()。

    week
  • 剑指offer 19:正则表达式匹配

    请实现一个函数用来匹配包括’.‘和’*‘的正则表达式。模式中的字符’.'表示任意一个字符,而‘*’表示它前面的字符可以出现任意次(包含0次)。 在本题中,匹配是...

    用户1148523
  • 『每天可视化』印度沉重的嫁妆文化

    印度的女性的不平等的问题一直是非常沉重的话题,针对印度女性的传统的陋习很多,嫁妆文化也是非常严重的问题。沉重的嫁妆成了女方整个家庭负担,甚至酿成了人间惨剧。

    alenmusk
  • 百度Echarts图表在Vue项目的完整引入以及按需加载

    近日在项目中需要进行图表展示,百度的Echarts图表是非常合适的一个选择。项目是vue-cli搭建的,如何在项目中引入Echarts就是一个问题了。亲自动手实...

    胡哥有话说
  • 腾讯云 windows 2019 实例镜像

    腾讯云目前还没正式支持windows2019,但本公司需要使用其linux子系统,所以不得已,自行制作了一个2019的镜像。在腾讯后台的帮助下,成功安装。

    用户5642012
  • 业界 | 反GAN传统,Petuum自动驾驶新研究提出从复杂真实图像生成简单虚拟表征以预测驾驶指令

    机器之心
  • 深度学习平台技术演进

    2017年12月22日,袁进辉(老师木)代表OneFlow团队在全球互联网架构大会上海站做了《深度学习平台技术演进》的报告,小编对报告内容作简要梳理注解,以飨读...

    企鹅号小编
  • 腾讯数平精准推荐 | OCR技术之识别篇

    本文介绍了腾讯数平精准推荐团队的OCR识别算法,包括识别算法的演进之路以及4个代表性方法。

    腾讯大数据

扫码关注云+社区

领取腾讯云代金券