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

【算法Hot100系列】正则表达式匹配

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
img

  • 推荐: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.解题思路

基础图示:

image-20231217171736474

分情况讨论:

image-20231217171752974

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 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙

img

相关文章:

【算法Hot100系列】正则表达式匹配

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

html 基础学习笔记

Date:20231212 html标签 基础学习笔记 一、web和internet 1.1、Internet简介 Internet 是一个全球性的计算机互联网络&#xff0c;中文名称有"因特网"、“国际互联网”、“网际网”、"交互网络"等Internet提供的主要服务 Telnet、Email、www、BBS、FTP等…...

7-4 天梯赛的善良

天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内&#xff0c;使得每个参赛的学生都有能做出来的题目&#xff0c;并且最厉害的学生也要非常努力才有可能得到高分。 于是命题组首先将编程能力划分成了 106 个等级&#xff08;太疯狂了&#xff0c;这是假的&…...

案例精选|聚铭综合日志分析系统助力长房集团“智慧房产”信息化建设

长沙房产&#xff08;集团&#xff09;有限公司&#xff08;简称“长房集团”&#xff09;始创于2004年3月&#xff0c;是一家由长沙市人民政府授权组建的国有独资企业。截至2021年底&#xff0c;企业总资产逾452亿元&#xff0c;总开发面积1300多万平方米&#xff0c;已开发项…...

HarmonyOS给应用添加消息通知

给您的应用添加通知 通知介绍 通知旨在让用户以合适的方式及时获得有用的新消息&#xff0c;帮助用户高效地处理任务。应用可以通过通知接口发送通知消息&#xff0c;用户可以通过通知栏查看通知内容&#xff0c;也可以点击通知来打开应用&#xff0c;通知主要有以下使用场景…...

【C语言】cache和程序访问的局部性对程序性能的影响

文章目录 1&#xff0e;源程序比较其性能影响2&#xff0e;内存分配&#xff08;1&#xff09;静态存储区&#xff08;static&#xff09;&#xff1a;&#xff08;2&#xff09;栈区&#xff08;stack&#xff09;&#xff1a;&#xff08;3&#xff09;堆区&#xff08;heap&…...

数字棱形(课程F)

输入1个整数N&#xff0c;输出N行的如下形状的数字棱形。 例如&#xff1a;N4时&#xff1a; ___1 __222 _33333 4444444 _33333 __222 ___1 (注&#xff1a;上面使用下划线’_’表示空格&#xff0c;以避免看不清造成误解) 输入格式 第一行1个正整数&#xff1a;N&#xff0…...

如何查看PHP信息

创建一个 PHP 文件&#xff0c;比如 info.php&#xff0c;在其中添加以下代码&#xff1a; <?php phpinfo(); ?>访问这个文件&#xff08;例如&#xff0c;在浏览器中输入 http://localhost/info.php&#xff09;&#xff0c;它会显示 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小时对系统进行人工监控&#xff0c;那么如果程序出现异常错误时要如何排查呢&#xff1f;并且系统在运行时做了哪些事情我们又从何得知呢&#xff1f;这个时候日志这个概念就出现了&#xff0c;日志的出现对系…...

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主要需要构建两个镜像&#xff0c;第一个为基础镜像&#xff0c;以centos7为基础构建新的基础镜像base.Dockerfile,第二个镜像为服务部署镜像server.Dockerfile&#xff0c;以第一个镜像base.Dockerfile构建出的镜像为基础镜像进行构建 整个基础镜像的构…...

登录校验,JWT令牌技术,过滤器(Filter)拦截器(interceptor)

登录功能&#xff1a; 前端传递json格式的数据。username&#xff08;用户名&#xff09;password&#xff08;密码&#xff09;。controller层对数据进行接收&#xff0c;由于是接收json格式的数据&#xff0c;所以我们把它封装到一个对象里面&#xff0c;由于登录是员工进行登…...

springCloud项目打包如何把jar放到指定目录下

springCloud项目打包如何把jar发放到指定目录下 maven-antrun-plugin springCloud微服务打包jar&#xff0c;模块过多&#xff1b;我的项目模块结构如下&#xff1a; 我把实体类相关的单独抽离一个模块在service-api下服务单独写在service某块下&#xff0c; 每个模块的jar都…...

vue中2种取值的方式

1.url是这种方式的&#xff1a;http://localhost:3000/user/1 取得参数的方式为&#xff1a;this.$route.params.id 2.url为get方式用&#xff1f;拼接参数的&#xff1a;http://localhost:3000/user?phone131121123&companyId2ahttp://localhost:3000/ 取得参数值的方式…...

Python基础05-函数

零、文章目录 Python基础05-函数 1、函数的作用及其使用步骤 &#xff08;1&#xff09;函数的作用 在Python实际开发中&#xff0c;我们使用函数的目的只有一个“让我们的代码可以被重复使用” 函数的作用有两个&#xff1a; ① 代码重用&#xff08;代码重复使用&#xf…...

Ubuntu 设置共享文件夹

一、在Windows中建立一个英文的文件夹 注意&#xff1a;新建文件夹的名称一定要是英文的&#xff0c;不能出现中文的路径&#xff08;可能出现问题&#xff09; 二、在VMware中添加共享文件 3: VMware安装VMware Tools 一般安装成功桌面上会显示这个安装包&#xff0c;&…...

操作系统期末复习-内存管理

一、内存管理 分页存储管理&#xff0c;是将一个进程的逻辑地址空间分成若干个大小相等的片&#xff0c;称为页面或页&#xff0c;并为各页加以编号&#xff0c;从0开始&#xff0c;如第0页、第1页等。相应地&#xff0c;也把内存空间分成与页面相同大小的若干个存储块&#xf…...

基于YOLOv8深度学习的西红柿成熟度检测系统【python源码+Pyqt5界面+数据集+训练代码】目标检测、深度学习实战

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…...

大数据存储技术(3)—— HBase分布式数据库

目录 一、HBase简介 &#xff08;一&#xff09;概念 &#xff08;二&#xff09;特点 &#xff08;三&#xff09;HBase架构 二、HBase原理 &#xff08;一&#xff09;读流程 &#xff08;二&#xff09;写流程 &#xff08;三&#xff09;数据 flush 过程 &#xf…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

手游刚开服就被攻击怎么办?如何防御DDoS?

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

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

页面渲染流程与性能优化

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

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...

深度解析:etcd 在 Milvus 向量数据库中的关键作用

目录 &#x1f680; 深度解析&#xff1a;etcd 在 Milvus 向量数据库中的关键作用 &#x1f4a1; 什么是 etcd&#xff1f; &#x1f9e0; Milvus 架构简介 &#x1f4e6; etcd 在 Milvus 中的核心作用 &#x1f527; 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...

CppCon 2015 学习:Reactive Stream Processing in Industrial IoT using DDS and Rx

“Reactive Stream Processing in Industrial IoT using DDS and Rx” 是指在工业物联网&#xff08;IIoT&#xff09;场景中&#xff0c;结合 DDS&#xff08;Data Distribution Service&#xff09; 和 Rx&#xff08;Reactive Extensions&#xff09; 技术&#xff0c;实现 …...