当前位置: 首页 > news >正文

剑指 Offer 19. 正则表达式匹配

摘要

剑指 Offer 19. 正则表达式匹配

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

一、动态规划解析

假设主串为A,模式串为B从最后一步出发,需要关注最后进来的字符。假设A的长度为n ,B的长度为m ,关注正则表达式B 的最后一个字符是谁,它有三种可能,正常字符、∗ 和 .(点),那针对这三种情况讨论即可,如下:

  • 如果B的最后一个字符是正常字符,那就是看 A[n−1]是否等于 B[m−1],相等则看A0..n−2与 B0..m−2,不等则是不能匹配,这就是子问题。
  • 如果B的最后一个字符是.,它能匹配任意字符,直接看 A0..n−2与B0..m−2。
  • 如果B的最后一个字符是*它代表 B[m−2]=c可以重复0次或多次,它们是一个整体 c∗
  •        情况一:A[n−1]是0个c,B最后两个字符废了,能否匹配取决于 A0..n−1和 B0..m−3是否匹配。
  •       情况二:A[n−1]是多个c中的最后一个(这种情况必须 A[n−1]=c或者 c=′.’),所以A匹配完往前挪一个,B继续匹配,因为可以匹配多个,继续看 A0..n−2和 B0..m−1​是否匹配。

转移方程

f[i][j]代表A 的前i个和B的前j个能否匹配

  • 对于前面两个情况,可以合并成一种情况 f[i][j]=f[i−1][j−1]
  • 对于第三种情况,对于c∗分为看和不看两种情况
  •       不看:直接砍掉正则串的后面两个, f[i][j]=f[i][j−2]
  •        看:正则串不动,主串前移一个,f[i][j]=f[i−1][j]

初始条件

特判:需要考虑空串空正则

  • 空串和空正则是匹配的,f[0][0]=true
  • 空串和非空正则,不能直接定义true和false,必须要计算出来。(比如A='' '' ,B=a∗b∗c∗)
  •        非空串和空正则必不匹配,f[1][0]=...=f[n][0]=false
  •        非空串和非空正则,那肯定是需要计算的了。

大体上可以分为空正则和非空正则两种,空正则也是比较好处理的,对非空正则我们肯定需要计算,非空正则的三种情况,前面两种可以合并到一起讨论,第三种情况是单独一种,那么也就是分为当前位置是∗和不是∗两种情况了。我们开数组要开n+1,这样对于空串的处理十分方便。结果就是 f[n][m]。

package DP;/*** @Classname JZ19正则表达式匹配* @Description TODO* @Date 2023/3/3 19:42* @Created by xjl*/
public class JZ19正则表达式匹配 {public boolean isMatch(String A, String B) {int n = A.length();int m = B.length();boolean[][] f = new boolean[n + 1][m + 1];for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {//分成空正则和非空正则两种if (j == 0) {f[i][j] = i == 0;} else {//非空正则分为两种情况 * 和 非*if (B.charAt(j - 1) != '*') {if (i > 0 && (A.charAt(i - 1) == B.charAt(j - 1) || B.charAt(j - 1) == '.')) {f[i][j] = f[i - 1][j - 1];}} else {//碰到 * 了,分为看和不看两种情况//不看if (j >= 2) {f[i][j] |= f[i][j - 2];}//看if (i >= 1 && j >= 2 && (A.charAt(i - 1) == B.charAt(j - 2) || B.charAt(j - 2) == '.')) {f[i][j] |= f[i - 1][j];}}}}}return f[n][m];}
}

博文参考

《leetcode》

相关文章:

剑指 Offer 19. 正则表达式匹配

摘要 剑指 Offer 19. 正则表达式匹配 请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符&#xff0c;而*表示它前面的字符可以出现任意次&#xff08;含0次&#xff09;。在本题中&#xff0c;匹配是指字符串的所有字符匹配整个模式。例如&#x…...

CSS——学成在线案例

&#x1f353;个人主页&#xff1a;bit.. &#x1f352;系列专栏&#xff1a;Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法 HTML和CSS3 目录 1.案例准备工作 2.CSS属性书写顺序&#xff08;重点&#xff09; 3.页面布局整体思路 4.头部的制作​编辑 5.banner制作…...

元数据的类型

元数据通常分为三种类型&#xff1a;业务元数据、技术元数据和操作元数据。这些类别使人们能够理解属于元数据总体框架下的信息范围&#xff0c;以及元数据的产生过程。也就是说&#xff0c;这些类别也可能导致混淆&#xff0c;特别是当人们对一组元数据属于哪个类别或应该由谁…...

LEAP模型的能源环境发展、碳排放建模预测及不确定性分析

LEAP&#xff08;Long Range Energy Alternatives Planning System/ Low emission analysis platform&#xff0c;长期能源可替代规划模型&#xff09;是一种自下而上的能源-环境核算工具&#xff0c;由斯德哥尔摩环境研究所和美国波士顿大学联合研发。该模型与情景分析法紧密结…...

C# Task详解

1、Task产生背景 Task出现之前&#xff0c;微软的多线程处理方式有&#xff1a;Thread→ThreadPool→委托的异步调用&#xff0c;虽然也可以基本业务需要的多线程场景&#xff0c;但它们在多个线程的等待处理方面、资源占用方面、线程延续和阻塞方面、线程的取消方面等都显得比…...

Blob分析+特征

Blob分析特征0 前言1 概念2 方法2.1 图像采集2.2 图像分割2.3 特征提取3 主要应用场景&#xff1a;0 前言 在缺陷检测领域&#xff0c;halcon通常有6种处理方法&#xff0c;包括Blob分析特征、Blob分析特征差分、频域空间域、光度立体法、特征训练、测量拟合&#xff0c;本篇博…...

4EVERLAND 的 IPFS Pinning 服务:4EVER Pin

我们很高兴地宣布 4EVERLAND Storage 的一个令人兴奋的补充&#xff0c;即 4EVER Pin。什么是 4EVER Pin&#xff1f;您可能已经知道星际文件系统或IPFS是一个分布式存储网络&#xff0c;来自世界各地的计算机组成节点共享数据。通常&#xff0c;在IPFS中获取一条数据时&#x…...

activiti整合springBoot其他操作

如果单纯使用activiti进行流程的自动控制&#xff0c;是可以实现的。但是通常我们都需要结合自定义的表&#xff0c;便于在流程执行中更加清晰的看到每一个流程实例节点的具体信息。关联自定义表与activiti表才能完成真正的业务 BusinessKey关联 // 定义businessKey Test pub…...

深度探索C++预编译头机制

深度详见预编译头&#xff0c;以vs编译器实现的预编译头管理为例 预编译头是为了节省庞大的编译时间&#xff0c;采取的一种方法&#xff1b;C标准并没有规定如何实现预编译头机制&#xff1b;因此其具体实现方式由编译器供应商自行决定。 下面就以VS中观测的结果为例进行说明…...

Leaflet基础入门教程(一)

leaflet是一个前端的轻量的gis框架,为什么说它轻量呢。因为相比于传统的“庞大的”GIS框架比如openlayers和mapbox,leaflet不仅代码体积小,而且API构成也极为简单。是GIS行业小白入门级别学习的最好的框架,没有之一。 那么话不多说我们首先来学习一下如何使用leaflet搭建一…...

《强化学习导论》之6.5 Q-Learning

Q-Learning:Off-Policy TD Control强化学习的早期突破之一是开发了一种称为Q学习的非策略TD控制算法&#xff08;Watkins&#xff0c;1989&#xff09;。其最简单的形式&#xff0c;定义为(6.8)在这种情况下&#xff0c;学习的动作-值函数Q直接近似于最优动作-值函数&#xff0…...

5年软测,女朋友跑了俩,2年外包感觉自己废了一半,怎么办?

17年毕业&#xff0c;校招毕业就进入一家软件公司&#xff0c;干了2年的点工&#xff0c;随后进入一家外包公司工作至今&#xff0c;安逸使人堕落不知进取&#xff0c;加之随着近年的环境不景气&#xff0c;谈了多年将要结婚的女朋友也因为我的心态和工资要跟我闹分手我想改变现…...

【JavaWeb】HTML常用标签

HTML标签结构 HTML语言主要都是由标签构成的。 标签名 在 <> 中 如<body> 标签大部分成对出现&#xff0c;代表开始和结束 如 <body>标签中的内容</body> 少部分单个出现&#xff0c;叫单标签 </br> 代表换行 标签中可以加属性&#xff0c;多个…...

python编程:查找某个文件夹下所有的文件,包括子文件加下的所有文件,读取指定类型的文件

目录 一、实现要求 二、代码实现 三、效果测试 一、实现要求 1、在电脑上有一个文件夹&#xff0c;该文件夹下面还有子文件夹&#xff0c;具体层级不清楚&#xff0c;需要实现将该文件夹下所有的文件路径读取出来&#xff1b; 2、在1的基础上&#xff0c;只需读取指定类型的文…...

测试外包干了5年,感觉自己已经废了····

前两天有读者想我资讯&#xff1a; 我是一名软件测试工程师&#xff0c;工作已经四年多快五年了。现在正在找工作&#xff0c;由于一直做的都是外包的项目。技术方面都不是很深入&#xff0c;现在找工作都是会问一些&#xff0c;测试框架&#xff0c;自动化测试&#xff0c;感…...

C++17 文件与目录操作 <filesystem>

目录 路径操作 目录遍历 文件检查和操作 总结 每次写C进行目录操作时&#xff0c;我一般都是调平台的SDK&#xff0c;尤其是win32 api 非常难记&#xff0c;于是查一下文档看看有没有和Python中os模块一样好用的库。 于是发现 filesystem&#xff0c;从来没用过&#xff0…...

Python 如何安装 MySQLdb ?

人生苦短 我用python Python 标准数据库接口为 Python DB-API&#xff0c; Python DB-API为开发人员提供了数据库应用编程接口。 Python 数据库接口支持非常多的数据库&#xff0c; 你可以选择适合你项目的数据库&#xff1a; GadFlymSQLMySQLPostgreSQLMicrosoft SQL Serve…...

总被程序员坑?你需要了解API接口

编辑导读&#xff1a;程序员是公司里的技术岗&#xff0c;也是产品经理最密切的合作伙伴。但是&#xff0c;程序员能看懂产品经理的工作&#xff0c;产品经理却不一定能明白程序员的工作&#xff0c;因此也常常被无良程序员坑。本文就从API接口的维度&#xff0c;浅析API的概念…...

信息系统基本知识(四)新技术

大纲 信息系统与信息化信息系统开发方法常规信息系统集成技术软件工程新一代信息技术信息系统安全技术信息化发展与应用信息系统服务管理信息系统服务规划企业首席信息管及其责任 1.5 新一代技术 1.5.1 物联网 概念&#xff1a;&#xff08;The Internet of Things&#xf…...

jeesite多环境配置

jeesite多环境配置 参考网址&#xff1a; https://blog.csdn.net/shaoming314/article/details/129115912?spm1001.2014.3001.5501 开源项目地址&#xff1a; https://gitee.com/thinkgem/jeesite Spring Spring MVC mybatis Ehcache shiro mysql jsp (主要技术栈) 项目…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Vue 模板语句的数据来源

&#x1f9e9; Vue 模板语句的数据来源&#xff1a;全方位解析 Vue 模板&#xff08;<template> 部分&#xff09;中的表达式、指令绑定&#xff08;如 v-bind, v-on&#xff09;和插值&#xff08;{{ }}&#xff09;都在一个特定的作用域内求值。这个作用域由当前 组件…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

CTF show 数学不及格

拿到题目先查一下壳&#xff0c;看一下信息 发现是一个ELF文件&#xff0c;64位的 ​ 用IDA Pro 64 打开这个文件 ​ 然后点击F5进行伪代码转换 可以看到有五个if判断&#xff0c;第一个argc ! 5这个判断并没有起太大作用&#xff0c;主要是下面四个if判断 ​ 根据题目…...