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事务传播行为的实现原理是什么?…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...

给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
go 里面的指针
指针 在 Go 中,指针(pointer)是一个变量的内存地址,就像 C 语言那样: a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10,通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...
C#最佳实践:为何优先使用as或is而非强制转换
C#最佳实践:为何优先使用as或is而非强制转换 在 C# 的编程世界里,类型转换是我们经常会遇到的操作。就像在现实生活中,我们可能需要把不同形状的物品重新整理归类一样,在代码里,我们也常常需要将一个数据类型转换为另…...