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

（leetcode算法题）10. 正则表达式匹配

news 来源：原创 2025/7/15 20:29:48

10. 正则表达式匹配 - 力扣（LeetCode）

此题的要求一个字符串 s 和一个字符规律 p之间支持 '.' 和 '*' 的正则表达式匹配

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

保证每次出现字符 * 时，前面都匹配到有效的字符也就是说p中所有的 * 字符前的那个字符只会是 . 或者字母
示例 1：输入：s = "a", p = ".*" 输出：true
示例 2：输入：s = "aab", p = "c*a*b" 输出：true
示例 3：输入：s = "a", p = "a*" 输出：true
示例 4：输入：s = "a", p = ".*a" 输出：true

根据经验和题目要求，两个字符串的关系可以考虑二维dp表，

能够解决的leetcode中的1143. 最长公共子序列、72. 编辑距离中dp的建立相似，

dp[i][j]表示p[0.j]区间内的子串是否能够匹配s[0,i]区间内的子串

状态转移方程：根据 p 切出来的子串中的最后一个字符来分情况讨论，这种按两个子串的最后一个字符的取值来分情况讨论的方式，也是推导状态转移方程的普遍步骤，

记记dp[i][j] = x; dp[i - 1][j] = y; dp[i][j - 2] = z dp[i - 1][j - 1] = w

则当p[j - 1] 为字母或者点号时，

只用通过 w 和 (s[i - 1] == p[j - 1] || p[j - 1] == '.')这个表达式是否为真就能更新dp[i][j]

当p[j - 1] 为星号时，

只用通过y 和 z 和(s[i - 1] == p[j - 2] || p[j - 2] == '.') 这个表达式是否为真就能更新dp[i][j]

图一

读者可能会问了，道理我都懂，为什么使用了dp[i][j - 2] 来更新dp[i][j]，而dp[i][j - 1]却没有使用？

让我们来看看图一中出现p[j - 1] == '*' && p[j - 2] == '.' 的情况

此时可以选择产生空串，或者将产生一个点号、两个点号，等等

那么dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || ... dp[i - m][j - 2] || ... (1)

令i = u - 1

则有dp[u - 1][j] = dp[u - 1][j - 2] || dp[u - 2][j - 2] || ... dp[u - m - 1][j - 2] || ... (2)

观察可知，可将（2）代入（1）中得到

dp[i][j] = dp[i][j - 2] || dp[i - 1][j]

让我们再来看看图一中出现p[j - 1] == '*' && p[j - 2] != '.' 的情况

此时可以选择产生空串，或者将产生一个p[j - 1]、两个p[j - 1]，等等

那么

dp[i][j] = dp[i][j - 2] || ((s[i -1] == p[j - 2]) && (dp[i - 1][j - 2])) || ... ((s[i - m] == p[j - 2]) && dp[i - m][j - 2] ) || ... (3)

令i = v - 1

则有dp[v - 1][j] = dp[v - 1][j - 2] || ( (s[v - 2] == p[j - 2]) && (dp[v - 2][j - 2]) ) || ... ( (s[v - m - 1] == p[j - 2]) && (dp[v - m - 1][j - 2]) ) || ... (4)

观察可知，可将（4）代入（3）中，然后经过一些列的推导(具体步骤略)，可以得到

dp[i][j] = dp[i][j - 2] || ( (s[i -1] == p[j - 2]) && dp[i - 1][j])

知道这道题为什么用到了dp[i][j - 2]了吧，但是还有一个很重要的问题，就是在编写这道题的程序的时候，可以给这个dp表多加一行，多加一列，所以

上面在访问原数组是 s[i - 1] 代表的就是第 i 个元素

那么多加的这一行/列是否可以赋予这个题目场景下的具体意义呢？

多加的一行，可以赋予dp[0][j] 一个意义，其意义就是s作为一个空串，匹配p[0, j]

如果在这种定义下，dp[0][j]要想为true，j 和 p[j] 必须满足以下条件才能保证匹配

dp[0, j] 是形如 {{非星号}{星号} {非星号}{星号} {非星号}{星号} {非星号}{星号}}

而dp[i][0] 此时只有在dp[0][0]处会为true

class Solution {
public:bool isMatch(string s, string p) {int len1 = s.size();int len2 = p.size();vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));dp[0][0] = true;for(int j = 2; j <= len2; j += 2){if(p[j - 1] == '*'){dp[0][j] = true;}else{break;}}for(int i = 1; i <= len1; ++i){for(int j = 1; j <= len2; ++j){if(p[j - 1] != '*'){dp[i][j] = ((p[j - 1] == s[i - 1] || p[j - 1] == '.') && dp[i - 1][j - 1] == true);}else{dp[i][j] = ((dp[i][j - 2] == true) || ((p[j - 2] == s[i - 1] || p[j - 2] == '.') && (dp[i - 1][j] == true)));}}}return dp[len1][len2];}
};

（leetcode算法题）10. 正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode） 此题的要求一个字符串 s 和一个字符规律 p之间支持 . 和 * 的正则表达式匹配 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串…...

编程日记 2025/7/15 20:29:48

Hive性能调优考量

Hive作为大数据领域常见的数据仓库组件，在设计和开发阶段需要注意效率。影响Hive效率的不仅仅是数据量过大，数据倾斜、job（小文件过多）或者磁盘I/O过多、MapReduce分配不合理等因素都会对Hive的效率有影响。对Hive的调优可以从架构…...

编程日记 2025/7/15 8:17:45

2024-12-29-sklearn学习（26）模型选择与评估-交叉验证：评估估算器的表现今夜偏知春气暖，虫声新透绿窗纱。

文章目录 sklearn学习(26) 模型选择与评估-交叉验证：评估估算器的表现26.1 计算交叉验证的指标26.1.1 cross_validate 函数和多度量评估26.1.2 通过交叉验证获取预测 26.2 交叉验证迭代器26.2.1 交叉验证迭代器–循环遍历数据26.2.1.1 K 折26.2.1.2 重复 K-折交叉验…...

编程日记 2025/7/12 4:36:26

Spring Boot + MinIO 实现分段、断点续传，让文件传输更高效

一、引言在当今的互联网应用中，文件上传是一个常见的功能需求。然而，传统的文件上传方式在面对大文件或不稳定的网络环境时，可能会出现性能瓶颈和上传失败的问题。传统文件上传，就像是用一辆小推车搬运大型家具，一…...

编程日记 2025/7/13 11:09:13

获取用户详细信息-ThreadLocal优化

Thread全局接口可用，不用再重复编写。所以为了代码的复用，使用Thread。把之前的内容（函数的参数和map与username）注释掉，换为Thread传过来的内容（map与username）。因为Thread需要在拦截器里面…...

编程日记 2025/7/13 17:18:30

R语言6种将字符转成数字的方法，写在新年来临之际

咱们临床研究中，拿到数据后首先要对数据进行清洗，把数据变成咱们想要的格式，才能进行下一步分析，其中数据中的字符转成数字是个重要的内容，因为字符中常含有特殊符号，不利于分析，转成数字后才能…...

编程日记 2025/7/15 20:20:05

Go语言方法和接收器类型详解

Go语言方法和接收器类型详解 1. 方法接收器类型 1.1 值接收器值接收器方法不会改变接收器的状态，因为Go语言会在调用时复制接收器的值。因此，任何对接收器成员变量的修改都只会影响副本，而不会影响原始结构体实例。 type Person struct …...

编程日记 2025/7/15 12:52:26

Linux常用命令总结

目录查询java服务的pid查询pid上的进程占用的端口方法 1：使用 lsof 查询端口方法 2：使用 netstat 查询端口方法 3：使用 ss 命令查询端口 system相关命令查询java服务的pid JPS查询pid上的进程占用的端口要根据进程 ID（PID&am…...

编程日记 2025/7/13 20:12:03

Linux总结之CentOS Stream 9安装mysql8.0实操安装成功记录

Linux总结之CentOS Stream 9安装mysql8.0实操安装成功记录由于网上很多的mysql8.0安装教程都是老版本或者安装过程记录有问题，导致经常安装到一半需要删除重新安装。所以将成功的实操安装过程记录一下，方面后面查阅，大家还有问题的可以在此讨…...

编程日记 2025/7/15 20:23:48

ROS2软件架构全面解析-学习如何设计通信中间件框架

前言 ROS（Robot Operating System） 2 是一个用于开发机器人应用的软件平台，也称为机器人软件开发工具包 (SDK)。 ROS2是ROS1的迭代升级版本 ，最主要的升级点是引入DDS（Data Distribution Service）为基础的…...

编程日记 2025/7/15 13:37:01

基于微信小程序的校园自助打印系统

博主介绍：java高级开发，从事互联网行业六年，熟悉各种主流语言，精通java、python、php、爬虫、web开发，已经做了多年的设计程序开发，开发过上千套设计程序，没有什么华丽的语言，只有实…...

编程日记 2025/7/14 21:33:27

Linux命令——3.网络与用户

文章目录一、网络1.网络测试与诊断2.网络接口配置3.无线网络配置4.防火墙与网络管理6.防火墙管理1）firewalld命令2）iptables命令二、用户和群组1.管理员模式2.用户账户管理1）useradd创建2）usermod修改3）userdel 删除…...

编程日记 2025/7/10 18:01:37

2、redis的持久化

redis的持久化在redist当中，高可用的技术包括持久化，主从复制，哨兵模式，集群。持久化是最简单的高可用的方法，作用就是备份数据。即将数据保存到硬盘，防止进程退出导致数据丢失。 redis持久化方式&…...

编程日记 2025/7/13 12:41:55

建造者模式 Builder Pattern

在创建一个对象的时候，构造器参数有点多，而且有些参数还是可选的，再者还有不少同类型的，那就更应该使用 builder 模式了。使用 Builder 模式的初衷是把易变性（mutability）移动到Builder类，而…...

编程日记 2025/7/15 1:16:59

制作一个类似ChatGPT的AI对话网站，模型能力使用ChatGPT

要快速搭建一个类似ChatGPT的AI对话网站，并且使用类似ChatGPT的模型能力，可以考虑以下技术和工具： ### 1. **使用现有的AI模型平台** - **OpenAI API**: 如果你希望使用类似于ChatGPT的能力，OpenAI提供了强大的API服务&#xff08…...

编程日记 2025/7/15 11:13:37

LinuxC高级day2

1.在家目录下创建目录文件，dir a.dir下创建dir1和dir2 b.把当前目录下的所有文件拷贝到dir1中， c.把当前目录下的所有脚本文件拷贝到dir2中 d.把dir2打包并压缩为dir2.tar.xz e.再把dir2.tar.xz移动到dir1中 f.解压dir1中的压缩包 g.使用tree工具&#x…...

编程日记 2025/7/15 1:22:31

Word格式修改

经常修改格式，留下这篇汇总 Word的累加符号上下标变右标指定目录：word如何取消封面或者目录下方的页码，页码从正文开始加参考文献：【Word】怎样给论文添加引用参考文献删空白页： word中无法删除空白页怎么办&#xff…...

编程日记 2025/7/10 19:59:47

深度学习-稀疏卷积

步骤： 1、构建输入输出哈希表； 输入哈希表的键为激活点的索引，值为激活点的坐标；输出哈希表的键为激活点对应的输出点的索引，值为输出点的坐标。 2、构建规则书； 规则书的每一行包含4个值，分别是…...

编程日记 2025/7/14 12:35:46

Microsoft Visual Studio中的/MT, /MTd,/MD,/MDd分别是什么意思？

1. /MT，/MTd，/MD，/MDd的含义 /MT，/MTd，/MD，/MDd是 Microsoft Visual C 编译器的运行时库链接选项。它们决定了程序如何链接 C 运行时库（CRT）。具体含义如下： /MT&#x…...

编程日记 2025/7/14 11:12:32

交换机关于环路、接口绑定、链路聚合的相关知识

文章目录 1、对交换机SW-1进行配置，仅允许Host-1通过Ethernet0/0/1接口与Host-3和Host-4通信，Host-2无法与其他主机通信。2、关闭生成树协议，验证环路造成的影响3、关闭生成树协议通过链路聚合实现两条链路正常通信并提高链路可靠性。内容包…...

编程日记 2025/7/12 18:09:25

5.微服务灰度发布落地实践(rocketmq增强)

文章目录前言发送端灰度增强订阅端灰度增强前言上一篇分析了，在灰度发布实现中为什么要对消息队列灰度发布进行增强。本篇主要介绍如何实现rocketmq 灰度发布的增强. 发送端灰度增强订阅端灰度增强...

编程日记 2025/7/3 15:19:42

32单片机从入门到精通之开发环境——库文件（六）

每个人都有自己的追求和梦想，但要实现这些梦想并不容易。在追逐梦想的路上，我们会遇到各种困难和挫折，甚至会感到无助和失望。然而，正是这些困难和挫折让我们更加坚韧和坚定地追求自己的目标。不要害怕失败，失败只是暂…...

编程日记 2025/7/15 8:41:46

大电流和大电压采样电路

大电压采样电路： 需要串联多个电阻进行分压，从而一级一级降低电压，防止电阻损坏或者短路直接打穿MCU。为什么需要加电压跟随器：进行阻抗的隔离，防止MCU的IO阻抗对分压产生影响： 大电流检测电路&#xff…...

编程日记 2025/7/13 17:10:09

用户态和内核态？

目录一、定义与特点二、功能与权限差异三、安全性与稳定性四、系统调用与交互五、参考用户态和内核态是操作系统中的两种基本运行状态，它们各自具有不同的特点和权限，共同构成了操作系统的运行基础。以下是对用户态和内核态的详细解释&#x…...

编程日记 2025/7/15 18:32:35

Qt天气预报系统设计界面布局第四部分左边

Qt天气预报系统设计 1、第四部分左边的第一部分1.1添加控件1.2修改控件名字 2、第四部分左边的第二部分2.1添加控件2.2修改控件名字 3、第四部分左边的第三部分3.1添加控件3.2修改控件名字 4、对整个widget04l调整 1、第四部分左边的第一部分 1.1添加控件拖入一个widget&…...

编程日记 2025/7/13 1:18:17

【Spring MVC 常用注解】注解驱动开发的魔法

在 Spring MVC 中，注解可以说是开发者的“魔法棒”，通过简单的注解配置，开发者能够实现请求处理、参数绑定、响应返回等复杂功能，真正做到“少写代码多干活”。我们接下来就来一起看看 Spring MVC 中常用的注解，它们的…...

编程日记 2025/7/13 9:38:35

FFmpeg 4.3 音视频-多路H265监控录放C++开发二十一.4，SDP协议分析

SDP在4566 中有详细描述。 SDP 全称是 Session Description Protocol， 翻译过来就是描述会话的协议。主要用于两个会话实体之间的媒体协商。什么叫会话呢，比如一次网络电话、一次电话会议、一次视频聊天，这些都可以称之为一次会话。那为什…...

编程日记 2025/7/12 21:12:21

STM32 高级 WIFi案例1：测试AT指令

需求描述测试AT指令是否能够正常控制ESP32的wifi，比如重启、读取设备信息等。思路： stm32通过串口usart2向ESP32发布命令。ESP32通过串口1返回信息。配置： 第一步：对ESP32芯片烧录可以读取stm32命令的固件（fac…...

编程日记 2025/7/15 18:08:13

Mono里运行C#脚本18—mono_image_load_names

前面已经分析完成加载CLR的流表，接着下来就是使用前面分析的数据，更进一步来处理了。下面就是通过函数mono_image_load_names获得程序集的名称和模块名称。在CLI定义的文档里，表Assembly : 0x20： Assembly表结构信息，以下是该表各列的简要说明： HashAlgId: 这是一个4字…...

编程日记 2025/7/12 17:32:07

Java和Python区别: 应用领域与性能抉择的深度解析

文章目录 1. 引言2. 语言特性对比：灵活性与严谨性的碰撞3. 应用场景分析：专注任务的工具选择3.1 数据库交互：Java 的优势所在3.2 图像识别与计算：Python 的专长3.3 Web 开发 4. 高并发请求处理：架构设计与硬件选择4.1 …...

编程日记 2025/7/15 11:09:33

SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者

SQL Server详细使用教程(包含启动SQL server服务、建立数据库、建表的详细操作) 非常适合初学者文章目录目录前言一、启动SQL server服务的三种方法 1.不启动SQL server服务的影响 2.方法一：利用cmd启动SQL server服务 3.方法二：利用SQL Serv…...

编程日记 2025/7/15 18:01:05

基于Docker+模拟器的Appium自动化测试（二）

模拟器的设置打开“夜神模拟器”的系统设置，切换到“手机与网络”页，选中网络设置下的“开启网络连接”和“开启网络桥接模式”复选框，而后选择“静态IP”单选框，在IP地址中输入“192.168.0.105”，网关等内容不再赘述…...

编程日记 2025/7/12 21:58:36

CSS系列（47）-- Animation Timeline详解

前端技术探索系列：CSS Animation Timeline详解 ⏱️ 致读者：探索动画时间线的艺术 👋 前端开发者们， 今天我们将深入探讨 CSS Animation Timeline，这个强大的动画控制特性。基础概念 🚀 时间线定义 …...

编程日记 2025/7/15 4:53:03

1、pycharm、python下载与安装

1、去官网下载pycharm 官网：https://www.jetbrains.com/pycharm/download/?sectionwindows 2、在等待期间，去下载python 进入官网地址：https://www.python.org/downloads/windows/ 3、安装pycharm 桌面会出现快捷方式 4、安装python…...

编程日记 2025/7/15 10:06:32

【翻译】优化加速像素着色器执行的方法

中文翻译在回复我的 Twitter 私信时，我遇到了一个关于如何提高像素/片段着色器执行速度的问题。这是一个相当广泛的问题，具体取决于每个 GPU/平台和游戏内容的特性，但我在本帖中扩展了我“头脑风暴”式的回答，以便其他人也觉得有用。这不是一份详尽的清单，更像是一个高层…...

编程日记 2025/7/13 18:09:54

ZLib库使用详细教程以及标准ZLib函数和QT自带压缩函数比较

1. 下载Zlib 官网下载地址如下：http://www.zlib.net/ 2. 利用cmake编译zlib 有两种方法可以打开cmake-gui winR输入cmd打开命令行，在命令行中输入cmake-gui可以直接打开应用界面找到你一开始安装cmake的文件夹，在bin子文件夹中双击cmake-…...

编程日记 2025/7/3 18:06:36

android stdudio环境： gradle一直安装失败

一、一直显示如下错误 The specified Gradle distribution file:/home/wangqingyuan/.gradle/wrapper/dists/gradle-8.6-bin/gradle-8.6-bin.zip does not exist. 经分析，是因为应用本身设置了gradle版本的地址为本地： 应用目录：gradle/gra…...

编程日记 2025/7/15 17:14:09

2024年12月31日Github流行趋势

项目名称：free-programming-books 项目地址url：https://github.com/EbookFoundation/free-programming-books项目语言：HTML历史star数：344575今日star数：432项目维护者：vhf, eshellman, davorpa, MHM5000, …...

编程日记 2025/7/12 12:47:35

音视频入门基础：MPEG2-TS专题（24）——FFmpeg源码中，显示TS流每个packet的pts、dts的实现

音视频入门基础：MPEG2-TS专题系列文章： 音视频入门基础：MPEG2-TS专题（1）——MPEG2-TS官方文档下载音视频入门基础：MPEG2-TS专题（2）——使用FFmpeg命令生成ts文件音视频入门基础…...

编程日记 2025/7/15 19:46:59

设计模式の状态策略责任链模式

文章目录前言一、状态模式二、策略模式三、责任链模式前言本篇是关于设计模式中的状态模式、策略模式、以及责任链模式的学习笔记。一、状态模式状态模式是一种行为设计模式，核心思想在于，使某个对象在其内部状态改变时，改变该对象的行为…...

编程日记 2025/7/14 0:05:17

TI毫米波雷达原始数据解析之Lane数据交换

TI毫米波雷达原始数据解析之Lane数据交换背景Lane 定义Lane 确认确认LVDS Lane 数量的Matlab 代码数据格式参考背景解析使用mmWave Studio 抓取的ADC Data Lane 定义芯片与DCA100之间的数据使用LVDS接口传输，使用mmWave Studio 配置过程中有一个选项是LVDS L…...

编程日记 2025/7/15 18:43:45

使用pdfminer.sixmarkdownify pdfminer.six可以提取Pdf文本内容markdownify可以将文本内容写markdown文件安装 pip install pdfminer.six pip install markdownify实现 from pdfminer.high_level import extract_text from markdownify import markdownifydef pdf2markdo…...

编程日记 2025/7/11 3:20:32

win32汇编环境下，双击窗口程序内生成的listview列表控件的某行，并提取其内容的示例程序

;运行效果 ;双击后 ;上源码，仔细研究里面的几条备注就理解原理了 ;提取窗口程序内生成的listview列表控件的内容示例程序 ;抄下面源码，可以在radasm里面直接编译运行。主要的部分加了备注。 ;>>>>>>>>>>>>>>…...

编程日记 2025/7/12 11:22:46

对45家“AI+安全”产品/方案的分析

一. 关键洞察 “AI+安全”创新非常活跃，一片百家争鸣之势，赛道选择上，以事件分诊Incident Triage、安全辅助Security Copilots、自动化Automation三者为主为主，这充分反映了当前安全运营的主要需求，在产品理念选择上以 AI 和自动化为主，这确实又切合上了在关键…...

编程日记 2025/7/14 23:28:53

家用电器销售系统｜Java｜SSM｜JSP｜

【技术栈】 1⃣️：架构: B/S、MVC 2⃣️：系统环境：Windowsh/Mac 3⃣️：开发环境：IDEA、JDK1.8、Maven、Mysql5.7 4⃣️：技术栈：Java、Mysql、SSM、Mybatis-Plus、JSP、jquery,html 5⃣️数据库可…...

编程日记 2025/7/12 19:03:04

小程序租赁系统构建指南与市场机会分析

内容概要在当今竞争激烈的市场环境中，小程序租赁系统正崭露头角，成为企业转型与创新的重要工具。通过这个系统，商户能够快速推出自己的小程序，无需从头开发，节省了大量时间和资金。让我们来看看这个系统的核心功能吧…...

编程日记 2025/7/13 23:33:52

《XML Schema 字符串数据类型》

《XML Schema 字符串数据类型》 1. 引言 XML Schema 是一种用于描述和验证 XML 文档结构和内容的语言。在 XML Schema 中，字符串数据类型是一种基本的数据类型，用于表示文本数据。本文将详细介绍 XML Schema 中的字符串数据类型，包括其定义…...

编程日记 2025/7/13 11:25:20

探索框架领域的新兴技术：微框架与插件化框架的崛起

近年来，随着软件开发技术的快速发展，开发者对框架的需求也在不断变化。从传统的重量级框架到轻量级微框架，以及支持高度扩展性的插件化框架，技术生态系统日新月异。本文旨在介绍这些新兴框架技术中的一些小众但创新的理念与实现&a…...

编程日记 2025/7/14 10:54:26

【数据结构-单调队列】力扣2762. 不间断子数组

给你一个下标从 0 开始的整数数组 nums 。nums 的一个子数组如果满足以下条件，那么它是不间断的： i，i 1 ，…，j 表示子数组中的下标。对于所有满足 i < i1, i2 < j 的下标对，都有 0 < |nums[i1…...

编程日记 2025/7/12 6:23:53

【复盘】2024年终总结

工作重构风控系统今年上半年其实就是整体重构系统，经历了多次加班的，其中的辛酸苦辣只有自己知道，现在来看的话，其实对自己还有一定的成长，从这件事情上也明白绩效能不能拿到A，在分配的任务的时候就决…...

编程日记 2025/7/14 11:00:20

上面在访问原数组是 s[i - 1] 代表的就是第 i 个元素

相关文章：