当前位置: 首页 > 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…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Keil 中设置 STM32 Flash 和 RAM 地址详解

文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...