【算法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 <= 20
1 <= p.length <= 20
s
只包含从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 过程 …...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...

手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
Linux系统部署KES
1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor
1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx
“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网(IIoT)场景中,结合 DDS(Data Distribution Service) 和 Rx(Reactive Extensions) 技术,实现 …...