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

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题里最难的一题了... 本题首要的就是需要理解题意&#xff0c;翻了评论区我才发现之前一直理解的题意是错的。 我原来理解的 “ *匹配0次” 是指&#xff1a;*直接消失&#xff0c;不会影响到前面的字符。 但是*和前一个字符其实是连体的&#xff0…...

Vue前端开发中的输入限制与输入规则探究

前言 在Vue前端开发中&#xff0c;我们经常需要对用户的输入进行限制和规范&#xff0c;以确保数据的准确性和安全性。本文将介绍如何使用Vue的el-input组件来实现输入限制和输入规则&#xff0c;并提供相应的代码示例。 一、输入限制 最大长度限制 我们可以使用maxlength属…...

自己封装 vue3+ts 组件库并且发布到 NPM

自己封装 vue3ts 组件库并且发布到 NPM 创建项目 pnpm create vite配置 package.json 按照提示创建好项目&#xff0c;然后再 package.json 中进行如下配置&#xff1a; {"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. 数据库安全性和一致性 &#x1f44d; 点赞&#x…...

“毛细血管”的进化:华为分销业务如何让伙伴也有“高能级”

作者 | 曾响铃 文 | 响铃说 数字化蓬勃发展的大时代&#xff0c;除了那些中、大型企业&#xff0c;数量更为庞大的小微企业同样有借助数字化产品、服务来提升企业经营的需求&#xff0c;由此也带来了广袤的数字化分销市场。 这里处在聚光灯之外&#xff0c;很少被数字化时代…...

警惕!多本SCI/SSCI被剔除,9月SCI/SSCI期刊目录已更新~(附下载)

【SciencePub学术】 2023年9月20日&#xff0c;科睿唯安更新了Web of Science核心期刊目录。 继上次SCI期刊目录和SSCI期刊目录更新之后&#xff0c;本次9月更新共有9本期刊发生变动&#xff1a; • SCIE&#xff1a;有3本期刊不再被SCIE期刊目录收录(Editorial De-listing/Pr…...

一点整理

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

Vulnhub系列靶机---Deathnote: 1死亡笔记

文章目录 信息收集主机发现端口扫描目录扫描dirsearchgobusterdirb扫描 漏洞利用wpscan扫描Hydra爆破 总结 靶机文档&#xff1a;Deathnote: 1 下载地址&#xff1a;Download (Mirror) 难易程度&#xff1a;so Easy 信息收集 主机发现 端口扫描 访问靶机的80端口&#xff0c;报…...

从基础到高阶:史上最小白的Attention机制详解——揭秘人工智能中的核心技术

1. Encoder-Decoder 想象一下你正在和一个会说多种语言的朋友对话。你用中文对他说了一句话&#xff0c;他将其“编码”成他的“内部语言”&#xff0c;然后再“解码”成英语给你回复。在这个过程中&#xff0c;“编码”就是Encoder&#xff0c;而“解码”就是Decoder。 在机…...

9.20金融科技(比特币)

​ 比特币的起源和发展 2008年爆发全球金融危机&#xff0c;同年11月1日&#xff0c;一个自称中本聪&#xff08;Satoshi Nakamoto&#xff09;的人在P2P foundation网站上发布了比特币白皮书《比特币&#xff1a;一种点对点的电子现金系 &#xff0c;陈述了他对电子货币的新设…...

什么是内存碎片?

在嵌入式系统中&#xff0c;内存是十分有限而且是十分珍贵的&#xff0c;用一块内存就少了一块内存&#xff0c;而在分配中随着内存不断被分配和释放&#xff0c;整个系统内存区域会产生越来越多的碎片。 因为在使用过程中&#xff0c;申请了一些内存&#xff0c;其中一些释放…...

C语言堆排序

堆排序&#xff08;Heapsort&#xff09;是一种在时间复杂度上达到了最优的基于比较的排序算法。堆排序算法是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构&#xff0c;并同时满足堆积的性质&#xff1a;即子节点的键值或索引总是小于&#xff0…...

【学习笔记】CF573E Bear and Bowling

感觉贪心的做法比较自然&#x1f914;&#xff0c;推荐 这篇博客 非常经典牛逼的贪心思路&#xff1a; 考虑每次加入一个数&#xff0c;位置 i i i的贡献为 V i k i a i b i V_ik_i\times a_ib_i Vi​ki​ai​bi​&#xff0c;其中 k i k_i ki​表示 i i i以前被选的位置的…...

函数扩展之——内存函数

前言&#xff1a;小伙伴们又见面啦。 本篇文章&#xff0c;我们将讲解C语言中比较重要且常用的内存函数&#xff0c;并尝试模拟实现它们的功能。 让我们一起来学习叭。 目录 一.什么是内存函数 二.内存函数有哪些 1.memcpy &#xff08;1&#xff09;库函数memcpy &…...

【在线机器学习】River对流数据进行机器学习

River是一个用于在线机器学习的Python库。它旨在成为对流数据进行机器学习的最用户友好的库。River是crme和scikit-multiflow合并的结果。 https://github.com/online-ml/river 举个简单示例&#xff0c;将训练逻辑回归来对网站网络钓鱼数据集进行分类。下面介绍了数据集中的…...

第 4 章 串(串的块链存储实现)

1. 背景说明 该实现和链表的实现极为相似&#xff0c;只是将链接的内存拆分为具体的大小的块。 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 };//这里为了是将第一列的表头隐藏&#xff0c;就形成了合…...

go学习-JS的encodeURIComponent转go

背景 encodeURIComponent() 函数通过将特定字符的每个实例替换成代表字符的 UTF-8 编码的一个、两个、三个或四个转义序列来编码 URI&#xff08;只有由两个“代理”字符组成的字符会被编码为四个转义序列&#xff09;。 与 encodeURI() 相比&#xff0c;此函数会编码更多的字…...

MySQL索引、事务与存储引擎

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

【Spring面试】八、事务相关

文章目录 Q1、事务的四大特性是什么&#xff1f;Q2、Spring支持的事务管理类型有哪些&#xff1f;Spring事务实现方式有哪些&#xff1f;Q3、说一下Spring的事务传播行为Q4、说一下Spring的事务隔离Q5、Spring事务的实现原理Q6、Spring事务传播行为的实现原理是什么&#xff1f…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

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

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (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文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; 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…...