LeetCode 难题解析 —— 正则表达式匹配 (动态规划)

10. 正则表达式匹配

思路解析

这道题虽然看起来不难理解,但却存在多种可能,当然这种可能的数量是有限的,且其规律对于每一次判别都使用,所以自然而然就想到用 动态规划 的方法啦

接下来逐步分析可能的情况:

(s1 为 字符串 的字符数组(长度m),s2 为匹配规律的字符数组(长度n)

由于需要存储每次匹配是否成功的结果,所以需构造一个二维布尔数组,存放对应是否匹配成功

s2 的 每一个匹配字符有三种情况:正常字符、'.' 、'*', 所以可以以此分类

1. 如果s2[n-1] 是正常字符(不是'.' 或 ‘*’) , 则如果 s1[m-1] = s2[n-1], 这时如果前面都匹配成功,则该次也匹配成功,即取决于 s1[0...m-2] 和 s2[0...n-2]是否匹配,否则不能匹配。

2. 如果s2[n-1] 是 '.' 即可满足任意字符,则 s1[m-1] 一定和 '.' 匹配, 这时如果前面匹配成功,即

s1[0...m-2] 和 s2[0...n-2] 都匹配,则该次匹配成功。

3. 如果 s2[n-1] 是 '*' ,则s2[n-2]='x' 可以重复0次或多次,这时s2[n-2]和s2[n-1]为一个整体X,这时会出现两种情况,即s1[m-1] 是 0个字符'x',还是多个'x'中的最后一个

        i. 如果s1[m-1]是0个字符'x', 则s1[m-1]与s2的匹配规则整体X无关,这时只需看s1[0...m-1]      和  s2[0...n-3]是否匹配即可。

        ii. 如果s1[m-1]是多个'x'的最后一个, 则这时候s1[m-1]必须为'x' 或者 s2[n-2] 为’.' 任意字符, 满足该条件后能否匹配则看 s1[0...m-2] 和 s2[0....n-1] 是否匹配。

初始条件和边界情况:空串和空正则表达式匹配:f[0][0] = TRUE

代码详解

话不多说,上代码

class Solution {// 动态规划public boolean isMatch(String s, String p) {char[] s1 = s.toCharArray();char[] s2 = p.toCharArray();int m = s1.length;int n = s2.length;boolean[][] f = new boolean[m+1][n+1];for(int i = 0; i <= m; i++) {// 边界情况:空串和空正则表达式匹配f[i][0] = (i==0);for(int j = 1; j <= n; j++) {f[i][j] = false;// 不为'*'的情况: 则当s2[j-1]为任意字符'.' 或者s2[j-1]==s1[i-1]满足if(s2[j-1] != '*') {if(i > 0 && (s2[j-1]=='.' || s2[j-1]==s1[i-1])){// 按位或,若 f[i-1][j-1]为true,则f[i][j]为truef[i][j] |= f[i-1][j-1];}} else {// 为s2[j-1]'*'的情况: // 如果s1[i-1]为0个匹配字符, 那么f[i][j] 是否为true取决与 f[i][j-2], 即s1第i-1和s2第j-3比较if(j - 2 >= 0) {f[i][j] |= f[i][j-2];}// s2[j-2]=='.' 或者 s1[i-1]==s2[j-2] // 则 那么f[i][j] 是否为true取决与 f[i-1][j], 此时i必满足,所以看i-1if(i>0 && j -2 >= 0 && (s2[j-2]=='.' || s1[i-1]==s2[j-2])){f[i][j] |= f[i-1][j];}}}}return f[m][n];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/323917.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

3---Linux编译器gcc/g++

一、程序的翻译过程&#xff1a;ESc->iso 1.1预处理&#xff1a;c->c 主要功能&#xff1a;宏替换、头文件的展开、条件编译、去注释&#xff1b;目的是让代码变得纯粹。条件编译&#xff0c;可以实现对代码的裁剪。比如对于不同用户&#xff0c;设置不同的宏常量&…

详解分布式锁

知识点&#xff1a; 单体锁存在的问题&#xff1a; 单体锁&#xff0c;即单体应用中的锁&#xff0c;通过加单体锁&#xff08;synchronized或RentranLock&#xff09;可以保证单个实例并发安全 单体锁是JVM层面的锁&#xff0c;只能保证单个实例上的并发访问安全 如果将单…

java JMH 学习

JMH 是什么&#xff1f; JMH&#xff08;Java Microbenchmark Harness&#xff09;是一款专用于代码微基准测试的工具集&#xff0c;其主要聚焦于方法层面的基准测试&#xff0c;精度可达纳秒级别。此工具由 Oracle 内部负责实现 JIT 的杰出人士编写&#xff0c;他们对 JIT 及…

鸿蒙内核源码分析(任务切换篇) | 看汇编如何切换任务

在鸿蒙的内核线程就是任务&#xff0c;系列篇中说的任务和线程当一个东西去理解. 一般二种场景下需要切换任务上下文: 在线程环境下&#xff0c;从当前线程切换到目标线程&#xff0c;这种方式也称为软切换&#xff0c;能由软件控制的自主式切换.哪些情况下会出现软切换呢? 运…

【AutoGPT】踩坑帖(follow李鱼皮)

本文写于2024年5月7日 参考视频&#xff1a;AutoGPT傻瓜式使用教程真实体验&#xff01; 对应文章&#xff1a;炸裂的AutoGPT&#xff0c;帮我做了个网站&#xff01; 平台&#xff1a;GitPod 云托管服务 原仓库已经改动很大&#xff0c;应使用的Repo为&#xff1a;Auto-GPT-ZH…

应用层协议之 DNS 协议

DNS 就是一个域名解析系统。域名就是网址&#xff0c;类似于 www.baidu.com。网络上的服务器想要访问它&#xff0c;就得需要它对应的 IP 地址&#xff0c;同时&#xff0c;每个域名对对应着一个 / N个 IP 地址&#xff08;即对应多台服务器&#xff09;。 因此&#xff0c;为了…

如何编译不同目录下的两个文件

1.直接编译 2.打包成动静态库进行链接

【bug记录】清除僵尸进程,释放GPU显存

目录 1. 为什么会出现这种情况&#xff1f;2. 解决方案方法一&#xff1a;使用 fuser 命令方法二&#xff1a; 3. 小贴士 在进行深度学习或其他需要GPU支持的任务时&#xff0c;我们有时会发现虽然没有可见的进程在执行&#xff0c;但GPU资源却意外地被占用。这种情况往往会阻碍…

如何确保UDP文件传输工具有最低稳定的传输速度?

在当前日新月异的数字时代背景下&#xff0c;文件传输工具已经成为我们日常生活与工作中不可或缺的一部分&#xff0c;尤其针对那些频繁涉及即时数据交互与多媒体流通的场景。 UDP协议&#xff0c;以其突出的高速传输与低延迟特性&#xff0c;脱颖而出成为众多用户的首选。不过…

这3种深拷贝实现,你都知道吗?

目录&#xff1a; 1、JSON.parse 2、structuredClone 3、cloneDeep

实习报告怎么写?笔灵AI实习体验报告模版分享:AI产品前端实习生

实习报告怎么写&#xff1f;笔灵AI实习体验报告模版可以帮你 点击即可使用&#xff1a;https://ibiling.cn/scene/inex?fromcsdnsx 下面分享AI产品前端实习生的实习报告 尊敬的导师和领导们&#xff1a;首先&#xff0c;我想对你们表达我的诚挚感谢&#xff0c;感谢你们给我…

C# WinForm —— 12 ListBox绑定数据

ListBox加载大量数据时&#xff0c;避免窗体闪烁的方法&#xff1a; 在加载语句的前后分别加上 BeginUpdate()方法 和 EndUpdate()方法 指定一个集合为绑定的数据源 1. 首先&#xff0c;右键项目&#xff0c;添加类 2. 在新建的类文件中添加属性值信息 3. 构建初始化的对象…

LeetCode 142.环形链表Ⅱ

题目描述 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内…

Windows命令行一键安装、配置WSL的方法

本文介绍在Windows电脑中&#xff0c;通过命令行的方式&#xff0c;快速、方便安装适用于Linux的Windows子系统&#xff08;Windows Subsystem for Linux&#xff0c;WSL&#xff09;的方法。 WSL是由微软开发的一项功能&#xff0c;允许在Windows操作系统上运行Linux发行版系统…

Adobe-Premiere-CEP 扩展 入门-视频剪辑-去气口插件-Silence Remover

短视频&#xff0c;这两年比较火&#xff0c;不要再问为什么用Premiere&#xff0c;非常难用&#xff0c;为什么不用某影&#xff0c;某些国内软件非常接地气简单&#xff0c;又例如某音资深的视频短编辑就很好用了。。。 Premiere二次开发调试难&#xff0c;不如自己搞个cons…

Ftp笑脸漏洞(VSFTPD 2.3.4)复现(后门漏洞)

Ftp笑脸漏洞&#xff08;VSFTPD 2.3.4&#xff09;复现&#xff08;后门漏洞&#xff09; 一、原理二、复现准备三、漏洞复现四、Metasploit利用脚本复现 一、原理 vsftpd 是“ very secure FTP daemon ”的缩写&#xff0c;安全性是它的一个最大的特点。 vsftpd是一个 UNIX 类…

学习笔记——字符串(单模+多模+练习题)

单模匹配 Brute Force算法&#xff08;暴力&#xff09; 算法思想 母串和模式串字符依次配对&#xff0c;如果配对成功则继续比较后面位置是否相同&#xff0c;如果出现匹配不成功的位置&#xff0c;则j&#xff08;模式串当前的位置&#xff09;从头开始&#xff0c;i&…

Qt——信号 和 槽

目录 概述 信号和槽的使用 自定义信号和槽 带参数的信号和槽 概述 在Linux系统中&#xff0c;我们也介绍了信号的产生、信号的检测以及信号的处理机制&#xff0c;它就是系统内部的通知机制&#xff0c;也可以是一种进程间通信的方式。在系统中有很多信号&#xff0c;我们可…

设计模式学习笔记 - 回顾总结:在实际软件开发中常用的设计思想、原则和模式

概述 本章&#xff0c;先来回顾下整个专栏的知识体系&#xff0c;主要包括面向对象、设计原则、编码规范、重构技巧、设计模式五个部分。 面向对象 相对于面向过程、函数式编程&#xff0c;面向对象是现在最主流的编程范式。纯面向过程的编程方法&#xff0c;现在已经不多见了…

数据结构中的栈(C语言版)

一.栈的概念 栈是一种常见的数据结构&#xff0c;它遵循后进先出的原则。栈可以看作是一种容器&#xff0c;其中的元素按照一种特定的顺序进行插入和删除操作。 压栈&#xff1a;栈的插入操作叫做进栈/压栈/入栈&#xff0c;入数据在栈顶。 出栈&#xff1a;栈的删除操作叫做…