leetcode 10. 正则表达式匹配
2023.9.20
感觉是目前做过dp题里最难的一题了...
本题首要的就是需要理解题意,翻了评论区我才发现之前一直理解的题意是错的。 我原来理解的 “ *匹配0次” 是指:*直接消失,不会影响到前面的字符。 但是*和前一个字符其实是连体的,所以说:*如果匹配0次,那么前一个字符就没了,消失了;*如果匹配1次,那么才相当于*消失了,不影响前面的字符;也就是说: *如果匹配n次,相当于前一个字符会出现n次。
理解了题意之后再来用dp算法做这道题。本题用的是二维bool型dp数组,dp[i][j]含义是:字符串s的前i个字符 和 字符串p的前j个字符 能否匹配。
再来看核心的递推公式。遍历的时候分为两种情况:
①s和p 的当前字符相等(这个相等包括p的当前字符是“_”,也算一种相等嘛!):那么可以想象一下,当前这两个字符相等了,像消消乐一样两字符消掉,两个指针各退一步,指向各自的前一个字符,当前dp数组的状态 转化为 之前dp数组的状态。即:dp[i][j] = dp[i - 1][j - 1];
②s和p 的当前字符不相等:两字符不相等了,还有补救措施,那就是p的字符如果为*的话,还有机会匹配。 那么此时又分为两种子情况:
- 当p的当前字符为"*"时:此时需要先判断一下*前面的字符和s的当前字符相不相等。如果不相等,说明*只能带着前面的字符一起消失了,即匹配0个:dp[i][j] = dp[i][j - 2]; 如果相等的话:那么*可以匹配0次、也可以匹配1次、也可以匹配多次,即dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];
- 当p的当前字符不为“*”时:那么直接就是false就行了,不过构建dp数组时是将所有位置都初始化为false了,所以这一步可以省略。
最后,dp[0][0]需要初始化为true,因为空字符串肯定是能匹配的嘛! 但是运行的时候有一个案例通不过:s=“aab”,p=“c*a*b” 。 翻看了评论区:有个方法就是分别在s和p之前加个空格:即
s = " " + s;
p = " " + p;
最后上代码:
class Solution {
public:bool isMatch(string s, string p) {s = " " + s; p = " " + p;vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false));dp[0][0] = true;for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= p.size(); j++) {//字符相同,或者p字符有万能符号。 (万能符号也可以理解为两字符相等)if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];} else if (p[j - 1] == '*') {if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {dp[i][j] = dp[i][j - 1] || dp[i][j - 2] || dp[i - 1][j];//分别对应*匹配1次、0次、多次的情况。} else {dp[i][j] = dp[i][j - 2]; //p字符串*号前面的字符 和 s字符串当前字符 不相等,只能让*匹配0次。}}}}return dp[s.size()][p.size()];}
};
相关文章:

leetcode 10. 正则表达式匹配
2023.9.20 感觉是目前做过dp题里最难的一题了... 本题首要的就是需要理解题意,翻了评论区我才发现之前一直理解的题意是错的。 我原来理解的 “ *匹配0次” 是指:*直接消失,不会影响到前面的字符。 但是*和前一个字符其实是连体的࿰…...
Vue前端开发中的输入限制与输入规则探究
前言 在Vue前端开发中,我们经常需要对用户的输入进行限制和规范,以确保数据的准确性和安全性。本文将介绍如何使用Vue的el-input组件来实现输入限制和输入规则,并提供相应的代码示例。 一、输入限制 最大长度限制 我们可以使用maxlength属…...
自己封装 vue3+ts 组件库并且发布到 NPM
自己封装 vue3ts 组件库并且发布到 NPM 创建项目 pnpm create vite配置 package.json 按照提示创建好项目,然后再 package.json 中进行如下配置: {"name": "tribiani-vue-tools","private": false,"version"…...
MySQL学习系列(6)-每天学习10个知识
目录 1. 管理和维护大量的数据库表和数据2. 检测和修复MySQL性能瓶颈3. MySQL的视图缓存4. 处理MySQL并发问题5. 函数索引和全文索引6. UNION ALL 和 UNION 的区别7. 存储引擎的选择8. 存储过程和触发器9. 数据表管理和优化10. 数据库安全性和一致性 👍 点赞&#x…...

“毛细血管”的进化:华为分销业务如何让伙伴也有“高能级”
作者 | 曾响铃 文 | 响铃说 数字化蓬勃发展的大时代,除了那些中、大型企业,数量更为庞大的小微企业同样有借助数字化产品、服务来提升企业经营的需求,由此也带来了广袤的数字化分销市场。 这里处在聚光灯之外,很少被数字化时代…...

警惕!多本SCI/SSCI被剔除,9月SCI/SSCI期刊目录已更新~(附下载)
【SciencePub学术】 2023年9月20日,科睿唯安更新了Web of Science核心期刊目录。 继上次SCI期刊目录和SSCI期刊目录更新之后,本次9月更新共有9本期刊发生变动: • SCIE:有3本期刊不再被SCIE期刊目录收录(Editorial De-listing/Pr…...

一点整理
(1) 美国在2010年以后开始流行数字化转型的。 在2010年以前, 2006年社交网络FB “YOU”:在2004-2006 Web2.0热之前,企业是无法直接触达到每个消费者的2006年Amazon电子商务:这个是我瞎凑的,但因…...

Vulnhub系列靶机---Deathnote: 1死亡笔记
文章目录 信息收集主机发现端口扫描目录扫描dirsearchgobusterdirb扫描 漏洞利用wpscan扫描Hydra爆破 总结 靶机文档:Deathnote: 1 下载地址:Download (Mirror) 难易程度:so Easy 信息收集 主机发现 端口扫描 访问靶机的80端口,报…...
从基础到高阶:史上最小白的Attention机制详解——揭秘人工智能中的核心技术
1. Encoder-Decoder 想象一下你正在和一个会说多种语言的朋友对话。你用中文对他说了一句话,他将其“编码”成他的“内部语言”,然后再“解码”成英语给你回复。在这个过程中,“编码”就是Encoder,而“解码”就是Decoder。 在机…...
9.20金融科技(比特币)
比特币的起源和发展 2008年爆发全球金融危机,同年11月1日,一个自称中本聪(Satoshi Nakamoto)的人在P2P foundation网站上发布了比特币白皮书《比特币:一种点对点的电子现金系 ,陈述了他对电子货币的新设…...

什么是内存碎片?
在嵌入式系统中,内存是十分有限而且是十分珍贵的,用一块内存就少了一块内存,而在分配中随着内存不断被分配和释放,整个系统内存区域会产生越来越多的碎片。 因为在使用过程中,申请了一些内存,其中一些释放…...
C语言堆排序
堆排序(Heapsort)是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子节点的键值或索引总是小于࿰…...
【学习笔记】CF573E Bear and Bowling
感觉贪心的做法比较自然🤔,推荐 这篇博客 非常经典牛逼的贪心思路: 考虑每次加入一个数,位置 i i i的贡献为 V i k i a i b i V_ik_i\times a_ib_i Vikiaibi,其中 k i k_i ki表示 i i i以前被选的位置的…...

函数扩展之——内存函数
前言:小伙伴们又见面啦。 本篇文章,我们将讲解C语言中比较重要且常用的内存函数,并尝试模拟实现它们的功能。 让我们一起来学习叭。 目录 一.什么是内存函数 二.内存函数有哪些 1.memcpy (1)库函数memcpy &…...
【在线机器学习】River对流数据进行机器学习
River是一个用于在线机器学习的Python库。它旨在成为对流数据进行机器学习的最用户友好的库。River是crme和scikit-multiflow合并的结果。 https://github.com/online-ml/river 举个简单示例,将训练逻辑回归来对网站网络钓鱼数据集进行分类。下面介绍了数据集中的…...

第 4 章 串(串的块链存储实现)
1. 背景说明 该实现和链表的实现极为相似,只是将链接的内存拆分为具体的大小的块。 2. 示例代码 1). status.h /* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H #define STATUS_H#define CHECK_NULL(pointer) if (!(pointer)) { \printf("FuncN…...

Element表格之表头合并、单元格合并
一、合并表头 el-table配置 :header-cell-style"headFirst"headFirst({ row, colunm, rowIndex, columnIndex }) {let base { background-color: rgba(67, 137, 249, 0.3), color: #333, text-align: center };//这里为了是将第一列的表头隐藏,就形成了合…...
go学习-JS的encodeURIComponent转go
背景 encodeURIComponent() 函数通过将特定字符的每个实例替换成代表字符的 UTF-8 编码的一个、两个、三个或四个转义序列来编码 URI(只有由两个“代理”字符组成的字符会被编码为四个转义序列)。 与 encodeURI() 相比,此函数会编码更多的字…...

MySQL索引、事务与存储引擎
索引 事务 存储引擎 一、索引1.1 索引的概念1.2 索引的实现原理1.2 索引的作用1.3 创建索引的依据1.4 索引的分类和创建1.4.1 普通索引 index1.4.2 唯一索引 unique1.4.3 主键索引 primary key1.4.4 组合索引(单列索引与多列索引)1.4.5 全文索引 fulltex…...

【Spring面试】八、事务相关
文章目录 Q1、事务的四大特性是什么?Q2、Spring支持的事务管理类型有哪些?Spring事务实现方式有哪些?Q3、说一下Spring的事务传播行为Q4、说一下Spring的事务隔离Q5、Spring事务的实现原理Q6、Spring事务传播行为的实现原理是什么?…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...

网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
【JavaSE】多线程基础学习笔记
多线程基础 -线程相关概念 程序(Program) 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序,比如我们使用QQ,就启动了一个进程,操作系统就会为该进程分配内存…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

Appium下载安装配置保姆教程(图文详解)
目录 一、Appium软件介绍 1.特点 2.工作原理 3.应用场景 二、环境准备 安装 Node.js 安装 Appium 安装 JDK 安装 Android SDK 安装Python及依赖包 三、安装教程 1.Node.js安装 1.1.下载Node 1.2.安装程序 1.3.配置npm仓储和缓存 1.4. 配置环境 1.5.测试Node.j…...