您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

算法:正则表达式匹配

时间:2022-07-13 16:13:02  来源:  作者:做架构师不做框架师

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

示例1

  • 输入: s = "aa",p = "a"
  • 输出: false
  • 解释: "a" 无法匹配 "aa" 整个字符串。

示例2

  • 输入: s = "aaa",p = "ab*.*"
  • 输出: true
  • 解释: 因为 '*' 表示零个或多个,这里 'b' 为 0 个, '.' 为 a , 重复2次。因此可以匹配字符串 "aaa"。

提示

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母以及字符 . 和 *,无连续的 '*'。

方法:动态规划

算法:正则表达式匹配

 

以示例2为例讲解:

  • 初始化取 dp[0][0] = true,代表匹配成功;
  • 当s取“a”的时候:p取“a”时候,成功;
  • p取“ab”的时候,失败;
  • p取“ab*”时候,*出现 0 次,即为 p 取 “a” 时候,成功;
  • p取“ab*.”的时候,失败,因为 s 只有一个字母,“.” 可以是任意字母,不满足;
  • p取“ab*.*”的时候,“.” 出现 0 次,“b”出现 0 次,成功。
  • 以此类推……

 

代码如下:

算法:正则表达式匹配

 

复杂度分析

  • 时间复杂度:O(MN),其中 M,N 分别为 s 和 p 的长度,状态转移需遍历整个 dp 矩阵。
  • 空间复杂度:O(MN),状态矩阵 dp 使用 O(MN) 的额外空间。

END

本文内容出处是力扣官网,希望和大家一起刷算法,在后面的路上不变秃但是变强!



Tags:正则表达式   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符,而'*'表示它前面的字符可以出现任意次(含0次)。在本题...【详细内容】
2022-07-13  Tags: 正则表达式  点击:(65)  评论:(0)  加入收藏
【写在最前】 我们在平时的编程学习中,经常会接触到“正则表达式”这个概念; 但是很多小白傻傻分不清楚它的正确用法以及适用场景,甚至是在查阅了很多资料之后仍然是云山雾罩。...【详细内容】
2022-05-18  Tags: 正则表达式  点击:(185)  评论:(0)  加入收藏
正则表达式(Regular expression)可用来检查文本中是否包含指定模式的字符串,通常是按行来处理(POSIX标准),因为.操作符通常不匹配换行符,如果要匹配多行怎么处理呢?本文介绍正则表达...【详细内容】
2022-03-22  Tags: 正则表达式  点击:(393)  评论:(0)  加入收藏
正则表达式,十分古老而又强大。熟悉掌握并使用,可以在编程时节省很多时间和精力,开发效率得到极大的提升。比如下面这十个正则表达式,是日常前JS开发中经常用到的,且都验证过,可直...【详细内容】
2022-02-25  Tags: 正则表达式  点击:(127)  评论:(0)  加入收藏
(1) 正则表达式【是什么】:特殊的序列。检测字符串是否与序列匹配。【有什么作用】:实现快速检索文本,或实现替换文本的操作。 实战:查看字符串是否包含python findal查找全部 r...【详细内容】
2022-02-25  Tags: 正则表达式  点击:(153)  评论:(0)  加入收藏
一、简介很多时候我们都需要用到一些验证的方法,有时候需要用正则表达式校验数据时,往往需要到网上找很久,结果找到的还不是很符合自己想要的。所以我把自己整理的校验帮助类分...【详细内容】
2021-12-27  Tags: 正则表达式  点击:(125)  评论:(0)  加入收藏
1. 什么是正则表达式正则表达式(Regular Expressions),也称为 “regex” 或 “regexp” 是使用单个字符串来描述、匹配一系列匹配某个句法规则的字符串,这样程序就可以将该模...【详细内容】
2021-11-26  Tags: 正则表达式  点击:(102)  评论:(0)  加入收藏
写在前面我们在日常的Java开发中,经常需要处理一些字符串,这个时候正则表达式是非常有用的。几乎在所有的编程语言中都支持正则表达式。以下我将压箱底多年的干货搬出来给大家...【详细内容】
2021-10-25  Tags: 正则表达式  点击:(121)  评论:(0)  加入收藏
正则作为处理字符串的一个实用工具,在Python中经常会用到,比如爬虫爬取数据时常用正则来检索字符串等等。正则表达式已经内嵌在Python中,通过导入re模块就可以使用,作为刚学Pyth...【详细内容】
2021-08-31  Tags: 正则表达式  点击:(164)  评论:(0)  加入收藏
打算给闺女买几本书,计划是列一个书单让闺女自己选。于是找到另一个还算不错的书单介绍页,可惜它不让复制,鼠标右键选中提示扫码以后就跳到学而思的网页让加老师的微信之类的。...【详细内容】
2021-08-10  Tags: 正则表达式  点击:(306)  评论:(0)  加入收藏
▌简易百科推荐
去年写了一篇文章手写一个虚拟DOM库,彻底让你理解diff算法介绍虚拟DOM的patch过程和diff算法过程,当时使用的是双端diff算法,今年看到了Vue3使用的已经是快速diff算法,所以也想...【详细内容】
2022-10-30  街角小林  今日头条  Tags:算法   点击:(4)  评论:(0)  加入收藏
前言CPU (Central Processing Unit)作为整个冯·诺依曼架构的控制与运算中心,终其一生都在执行没有边界的指令,用无差别的计算支撑起智能时代“算力取之不尽用之不竭”的...【详细内容】
2022-10-28  码洞  CSDN  Tags:算法   点击:(13)  评论:(0)  加入收藏
什么是散列表散列表又被称为哈希表,包含一个键key、一个值value它们之间的对应关系是一对一,散列表就提供了键key和值value的对应关系,基本结构如下。 键值不会重复所以通过键...【详细内容】
2022-10-25  Java面试365  今日头条  Tags:散列表   点击:(5)  评论:(0)  加入收藏
摘要深度学习在科学计算领域得到了广泛的应用,其算法被解决复杂问题的行业广泛使用。所有的深度学习算法都使用不同类型的神经网络来执行特定的任务。本文为大家带来基本的人...【详细内容】
2022-10-22  BigQuant  今日头条  Tags:算法   点击:(4)  评论:(0)  加入收藏
作者:小傅哥 博客:https://bugstack.cn沉淀、分享、成长,让自己和他人都能有所收获!一、前言:挂在树上!不知道你经历过HashMap的夺命连环问!为啥,面试官那么喜欢让你聊聊 HashMap?因...【详细内容】
2022-10-10  小傅哥    Tags:红黑树   点击:(19)  评论:(0)  加入收藏
前言在头条创作了一个月左右的时间,收获了50+粉丝,很是开心,我会把数据结构与算法的文章更新到底,第一次看我文章的同仁如果觉得不错的话就关注一下我哦,你的支持就是我创作的动...【详细内容】
2022-10-10  掂掂三生有幸  今日头条  Tags:数据结构   点击:(12)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(20)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(21)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(15)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)—&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(17)  评论:(0)  加入收藏
站内最新
站内热门
站内头条