【Leetcode】10. 正则表达式匹配
10. 正则表达式匹配(困难)



-
题解
-
如果从左向右进行匹配的话,需要考虑字符后是否有 * 。

-
因此选择从右向左扫描更为简单。
*前面肯定有一个字符,它像是一个拷贝器,能够复制前面的单个字符,甚至也可以把这个字符消除(出现 0 次)。
两个字符串是否匹配,取决于最右边的字符是否匹配,以及剩余的子串是否匹配。其中,「剩余的子串是否匹配」,就是本道题的子问题。

-
状态定义:定义
dp[i][j]为第一个字符串到 i 为止,第二个字符串到 j 为止,两个字符串是否匹配。如果匹配,dp[i][j] = true;如果不匹配,dp[i][j] = false。 -
子问题的考虑
-
情况一:s[i-1] 和 p[j-1] 匹配,即
s[i-1] == p[j-1] || p[j-1] == '.'。那么只需要考虑剩余的子串是否匹配,即dp[i][j] = dp[i-1][j-1];
-
情况二:s[i-1] 和 p[j-1] 不匹配。这时候不能直接认为两个字符串不匹配,而是需要进一步考虑
p[j-1] == '*'的情况。但是如果不是*,那么肯定不匹配。
对于
*,它可以匹配 0 个或多个字符。当s[i-1] 和 p[j-2] 匹配,且 p[j-1] == ‘*’ 时,需要考虑三种情况:*使dp[j-2]出现 0 次、1 次或 >=2次。只要其中一种情况能使得两个子串匹配,我们就可以继续考虑剩余子串是否匹配。状态转移方程为:dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];
当s[i-1] 和 p[j-2] 不匹配,且 p[j-1] == ‘*’ 时,可以利用*消除不匹配字符 p[j-2],考虑 s[i-1] 和 p[j-3] 是否匹配。状态转移方程为:dp[i][j] = dp[i][j-2];。
-
-
初始情况:当两个字符串都是空串的时候,一定匹配,因此
dp[0][0] = true;;当 s 为空时,如果 p 的右端字符是*,那么就可以使得 p 也变成空串;当 p 为空,两个字符串一定不匹配。
-
-
代码
class Solution { public:bool isMatch(string s, string p) {int m = s.size(), n = p.size();vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));// 两个空字符串一定匹配dp[0][0] = true;// 如果s为空串 p[j-1]=* 也能够匹配for(int j=1; j<=n; ++j){if(p[j-1] == '*'){dp[0][j] = dp[0][j-2];}}// 从右向左匹配for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){// s[i-1]和p[j-1]匹配if(s[i-1] == p[j-1] || p[j-1] == '.'){dp[i][j] = dp[i-1][j-1];}// s[i-1]和p[j-1]不匹配else{// p[j-1] == '*' 且 s[i-1]和p[j-2]匹配if(p[j-1] == '*'){dp[i][j] = dp[i][j-2];if(s[i-1] == p[j-2] || p[j-2] == '.'){dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j];}}}}}return dp[m][n];} }; -
收获
- 理解错了 * 的意思,* 类似于一个拷贝器 ,能匹配前一个元素,也能消除前一个元素(匹配零个)。
- 这道题需要考虑多种情况,感觉很难想得这么全面。
相关文章:
【Leetcode】10. 正则表达式匹配
10. 正则表达式匹配(困难) 题解 如果从左向右进行匹配的话,需要考虑字符后是否有 * 。 因此选择从右向左扫描更为简单。 *前面肯定有一个字符,它像是一个拷贝器,能够复制前面的单个字符,甚至也可以把这个…...
不得不说的结构型模式-装饰器模式
目录 装饰器模式是什么 下面是装饰器模式的一个通用的类图: 以下是使用C实现装饰器模式的示例代码: 下面是面试中关于桥接器模式的常见的问题: 下面是问题的答案: 装饰器模式是什么 装饰器模式是一种结构型设计模式ÿ…...
Flutter+YesAPI 快速构建零运维的APP
前言 移动互联网经过多年的发展,已经进入一个成熟的阶段,几乎每个公司都有自己的移动应用程序或移动网站。随着5G技术的不断发展,也带来了更高效的数据传输速度和更稳定的网络连接,这使得更多的应用程序和服务能够在互联网上运行&…...
使用Socks5代理保障HTTP传输的网络安全
一、引言 在互联网时代,网络安全越来越受到人们的关注,特别是在数据传输过程中,很容易出现信息泄露、窃听等安全问题。为了保障网络传输的安全性,我们可以使用代理服务器来进行传输,而Socks5代理是其中一种常用的代理…...
C语言入门篇——操作符篇
目录 1、操作符分类 2、操作符的属性 3、算术操作符 4、移位操作符 5、位操作符 6、赋值操作符 7、单目操作符 8、关系操作符 9、逻辑操作符 10、条件操作符 11、逗号操作符 12、下标引用、函数调用和结构成员 1、操作符分类 算术操作符(,-&…...
YOLOv7训练自己的数据集(txt文件,笔记)
目录 1.代码下载 2.数据集准备(.xml转.txt) (1)修改图像文件名 (2)图片和标签文件数量不对应,解决办法 (3).xml转.txt (4).txt文件随机划分出对应的训练…...
防止机械/移动硬盘休眠 - NoSleepHD
防止机械/移动硬盘休眠 - NoSleepHD 前言解决方案计算机硬盘移动硬盘 前言 机械硬盘休眠后唤醒需要一定时间,且频繁的启动和停止并不有利于硬盘的寿命,因此可根据自身需求防止机械硬盘休眠,下文以Win10系统为例介绍解决方案。 值得一提的是…...
(二)app自动化脚本录制回放
上一篇:(一)app自动化测试环境搭建(maciosairtest )_airtest环境搭建_要开朗的spookypop的博客-CSDN博客 注:后续都是用IOS设备来介绍自动化测试,安卓就不赘述了。 接上一篇,搭建好自动化测试环境后&#…...
STM32HAL库USART外设配置流程及库函数讲解
HAL库中USART外设配置流程及库函数讲解 一说到串口通信,及必须说一下aRS-232/485协议。232协议标准物理接口就是我们常用的DB9串口线 RS-232电平: 逻辑1:-15~-3 逻辑0: 3~15 COMS电平: 逻辑1:3.3 逻辑0&a…...
Qt 实现TCP通信和UDP通信
Qt 实现TCP通信和UDP通信 1、TCP通信 QT中实现TCP通信主要用到了以下类:QTcpServer、QTcpSocket、QHostAddress等; 使用QTcpServer来创建一个TCP服务器,在新的连接建立时,将新建立连接的socket添加到列表中,以便发送…...
完成近4亿元C轮融资+自研底盘域控,本土线控制动玩家“拼”了
显然,线控制动赛道已经进入白热化竞争阶段。 高工智能汽车研究院监测数据显示,2022年中国市场(不含进出口)乘用车前装搭载线控制动系统(One-Box,Two-Box)上险交付合计497.39万辆,同…...
【UE】一个简易的游戏计时器
效果 步骤 1. 打开“ThirdPersonGameMode” 创建两个整型变量,分别命名为“Seconds”、“Minutes” 在事件图表中添加如下节点,实现“Seconds”每秒加1 继续添加如下节点: 当秒数大于60时,就让分钟数1,然后将秒数重新…...
Leetcode力扣秋招刷题路-0455
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 455. 分发饼干 假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。 对每个孩子 i,都有一个胃口值 g[i]&#x…...
一小时学会CSS (上)
1、CSS是什么? CSS (Cascading Style Sheets)层叠样式表,是一种来为结构化文档,例如HTML 、XML 添加字体,间距和颜色等样式的计算机语言,扩展名是.CSS 。 2、CSS语法规则 CSS写在哪里,CSS写在…...
DockerImage镜像版本说明
参考文章 1、https://medium.com/swlh/alpine-slim-stretch-buster-jessie-bullseye-bookworm-what-are-the-differences-in-docker-62171ed4531d 2、https://stackoverflow.com/questions/52083380/in-docker-image-names-what-is-the-difference-between-alpine-jessie-stret…...
ROS学习第三十三节——Arbotix使用
https://download.csdn.net/download/qq_45685327/87718484 1.介绍 通过 URDF 结合 rviz 可以创建并显示机器人模型,不过,当前实现的只是静态模型,如何控制模型的运动呢?在此,可以调用 Arbotix 实现此功能。 Arboti…...
ElasticSearch第十九讲 ES-best fields,most fields策略
multi-field多字段搜索 假设有个网站允许用户搜索博客的内容,以下面两篇博客内容文档为例: PUT /my_index/my_type/1 {"title": "Quick brown rabbits","body": "Brown rabbits are commonly seen." }PUT /my_index/my_type/2 {&…...
Netty详解,5分钟了解,面试不用慌
1. 概述 1.1 Netty 是什么? Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty 是一个异步的、基于事件驱动的网络应用框架,用…...
Logstash学习
一、Logstash基础 1、什么是Logstash logstash是一个数据抽取工具,将数据从一个地方转移到另一个地方。下载地址:https://www.elastic.co/cn/downloads/logstash logstash之所以功能强大和流行,还与其丰富的过滤器插件是分不开的ÿ…...
【流畅的Python学习笔记】2023.4.22
此栏目记录我学习《流畅的Python》一书的学习笔记,这是一个自用笔记,所以写的比较随意 元组 元组其实是对数据的记录:元组中的每个元素都存放了记录中一个字段的数据,外加这个字段的位置。简单试试元组的特性: char…...
Unity3D中Gfx.WaitForPresent优化方案
前言 在Unity中,Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染(即CPU被阻塞),这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案: 对惹,这里有一个游戏开发交流小组&…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
