【算法Hot100系列】正则表达式匹配
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
- 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老
- 导航
- 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
- 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
- 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
- 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
- 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂
非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨
博客目录
- 一.题目描述
- 1.题目信息
- 2.题目地址
- 3.测试示例
- 4.提示信息
- 二.题解
- 1.动态规划
- 2.解题思路
- 3.注意事项
- 三.自我分析
- 1.解题思路
- 2.思考链路
一.题目描述
1.题目信息
给你一个字符串
s和一个字符规律p,请你来实现一个支持'.'和'*'的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个 字符串
s的,而不是部分字符串。
2.题目地址
题目地址
3.测试示例
示例 1:
输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
4.提示信息
提示:
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母,以及字符.和*。- 保证每次出现字符
*时,前面都匹配到有效的字符
二.题解
1.动态规划
public boolean isMatch(String s, String p) {final int n = s.length();final int m = p.length();boolean[][] dp = new boolean[n + 1][m + 1];dp[0][0] = true;//首行 s 为空字符串,因此当 p 的偶数位为 * 时才能够匹配(即让 p 的奇数位出现 0 次,保持 p 是空字符串)。//因此,循环遍历字符串 p ,步长为 2(即只看偶数位)。for (int j = 1; j <= m; j++) {if (p.charAt(j - 1) == '*') {dp[0][j] = dp[0][j - 2];}}// 填充动态规划数组for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {final char sc = s.charAt(i - 1);final char pc = p.charAt(j - 1);if (pc == '.' || sc == pc) {dp[i][j] = dp[i - 1][j - 1];} else if (pc == '*') {dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));}}}return dp[n][m];
}
2.解题思路
基础图示:

分情况讨论:

3.注意事项
j的位置不等于*
- 要求 i-1 和 j-1 之前的都要匹配
- 并且(s[i-1]等于 p[j-1] 或者 p[j-1]等于.
j的位置等于*
- 推算出 f(i,j)的表达式
- 演化出 f(i-1,j)的表达式
- 简化 f(i,j)的表达式,就是用 f(i-1,j)取代某一部分,状态转移方程
三.自我分析
1.解题思路
if 有思路开写
else去看相关标签,确定具体解题方法if 有思路开写else看提示信息if 有思路开写else看答案
2.思考链路
- 没有思路
- 多做,多思考
- 形成自己的肌肉记忆
- 多多调试
- 多总结
- 题解都看不懂,可以去 B 站看视频讲解
- 多回头看看以前的题目,温故而知新
觉得有用的话点个赞
👍🏻呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙
相关文章:
【算法Hot100系列】正则表达式匹配
💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...
html 基础学习笔记
Date:20231212 html标签 基础学习笔记 一、web和internet 1.1、Internet简介 Internet 是一个全球性的计算机互联网络,中文名称有"因特网"、“国际互联网”、“网际网”、"交互网络"等Internet提供的主要服务 Telnet、Email、www、BBS、FTP等…...
7-4 天梯赛的善良
天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内,使得每个参赛的学生都有能做出来的题目,并且最厉害的学生也要非常努力才有可能得到高分。 于是命题组首先将编程能力划分成了 106 个等级(太疯狂了,这是假的&…...
案例精选|聚铭综合日志分析系统助力长房集团“智慧房产”信息化建设
长沙房产(集团)有限公司(简称“长房集团”)始创于2004年3月,是一家由长沙市人民政府授权组建的国有独资企业。截至2021年底,企业总资产逾452亿元,总开发面积1300多万平方米,已开发项…...
HarmonyOS给应用添加消息通知
给您的应用添加通知 通知介绍 通知旨在让用户以合适的方式及时获得有用的新消息,帮助用户高效地处理任务。应用可以通过通知接口发送通知消息,用户可以通过通知栏查看通知内容,也可以点击通知来打开应用,通知主要有以下使用场景…...
【C语言】cache和程序访问的局部性对程序性能的影响
文章目录 1.源程序比较其性能影响2.内存分配(1)静态存储区(static):(2)栈区(stack):(3)堆区(heap&…...
数字棱形(课程F)
输入1个整数N,输出N行的如下形状的数字棱形。 例如:N4时: ___1 __222 _33333 4444444 _33333 __222 ___1 (注:上面使用下划线’_’表示空格,以避免看不清造成误解) 输入格式 第一行1个正整数:N࿰…...
如何查看PHP信息
创建一个 PHP 文件,比如 info.php,在其中添加以下代码: <?php phpinfo(); ?>访问这个文件(例如,在浏览器中输入 http://localhost/info.php),它会显示 PHP 的所有配置信息。在这个页面…...
Vue3+ts实现页面跳转及参数传递
## 列表页 <script lang"ts" setup> import { reactive, toRefs } from vue // 1 引入useRouter路由信息方法 import { useRouter } from vue-router // 2 获取实例 const router useRouter()const gotoDetail (index: string) > {router.push({path: …...
日志框架Log4j、JUL、JCL、Slf4j、Logback、Log4j2
1. JAVA日志框架 1.1 为什么程序需要记录日志 我们不可能实时的24小时对系统进行人工监控,那么如果程序出现异常错误时要如何排查呢?并且系统在运行时做了哪些事情我们又从何得知呢?这个时候日志这个概念就出现了,日志的出现对系…...
mybatis动态SQL-sql片段
1、建库建表 create database mybatis-example; use mybatis-example; create table emp (empNo varchar(40),empName varchar(100),sal int,deptno varchar(10) ); insert into emp values(e001,张三,8000,d001); insert into emp values(e002,李四,9000,d001); insert into…...
wvp-GB28181-pro 2.0+ZLMediaKit 使用Dockerfile制作镜像以及部署【CentOS7】
说明 部署gb28181和zlm主要需要构建两个镜像,第一个为基础镜像,以centos7为基础构建新的基础镜像base.Dockerfile,第二个镜像为服务部署镜像server.Dockerfile,以第一个镜像base.Dockerfile构建出的镜像为基础镜像进行构建 整个基础镜像的构…...
登录校验,JWT令牌技术,过滤器(Filter)拦截器(interceptor)
登录功能: 前端传递json格式的数据。username(用户名)password(密码)。controller层对数据进行接收,由于是接收json格式的数据,所以我们把它封装到一个对象里面,由于登录是员工进行登…...
springCloud项目打包如何把jar放到指定目录下
springCloud项目打包如何把jar发放到指定目录下 maven-antrun-plugin springCloud微服务打包jar,模块过多;我的项目模块结构如下: 我把实体类相关的单独抽离一个模块在service-api下服务单独写在service某块下, 每个模块的jar都…...
vue中2种取值的方式
1.url是这种方式的:http://localhost:3000/user/1 取得参数的方式为:this.$route.params.id 2.url为get方式用?拼接参数的:http://localhost:3000/user?phone131121123&companyId2ahttp://localhost:3000/ 取得参数值的方式…...
Python基础05-函数
零、文章目录 Python基础05-函数 1、函数的作用及其使用步骤 (1)函数的作用 在Python实际开发中,我们使用函数的目的只有一个“让我们的代码可以被重复使用” 函数的作用有两个: ① 代码重用(代码重复使用…...
Ubuntu 设置共享文件夹
一、在Windows中建立一个英文的文件夹 注意:新建文件夹的名称一定要是英文的,不能出现中文的路径(可能出现问题) 二、在VMware中添加共享文件 3: VMware安装VMware Tools 一般安装成功桌面上会显示这个安装包,&…...
操作系统期末复习-内存管理
一、内存管理 分页存储管理,是将一个进程的逻辑地址空间分成若干个大小相等的片,称为页面或页,并为各页加以编号,从0开始,如第0页、第1页等。相应地,也把内存空间分成与页面相同大小的若干个存储块…...
基于YOLOv8深度学习的西红柿成熟度检测系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战
《博主简介》 小伙伴们好,我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍感谢小伙伴们点赞、关注! 《------往期经典推…...
大数据存储技术(3)—— HBase分布式数据库
目录 一、HBase简介 (一)概念 (二)特点 (三)HBase架构 二、HBase原理 (一)读流程 (二)写流程 (三)数据 flush 过程 …...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
android13 app的触摸问题定位分析流程
一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...
PostgreSQL——环境搭建
一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在࿰…...

