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

力扣热门100题刷题笔记 - 10. 正则表达式匹配

力扣热门100题 - 10. 正则表达式匹配

题目链接:10. 正则表达式匹配

题目描述:

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例:

输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
输入:s = "aa", p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
输入:s = "ab", p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

提示:

1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符

解题思路(动态规划):

动态规划数组的定义: 我们使用一个二维数组 dp,其中 dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
初始化: 首先,dp[0][0] 表示空字符串和空正则表达式是匹配的,因此 dp[0][0] = true。
处理 '*' 的情况: 对于每个正则表达式中的 '*',我们需要考虑两种情况:'*' 匹配零个前面的元素:dp[i][j] = dp[i][j - 2]。'*' 匹配一个或多个前面的元素:dp[i][j] = dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')。
处理 '.' 和普通字符的情况: 如果当前字符匹配,即 p.charAt(j - 1) == '.' 或者 p.charAt(j - 1) == s.charAt(i - 1),则 dp[i][j] = dp[i - 1][j - 1]。
填充动态规划数组: 使用两层嵌套循环遍历字符串 s 和正则表达式 p,根据上述规则填充动态规划数组。
返回结果: 最终结果为 dp[m][n],其中 m 和 n 分别是字符串 s 和正则表达式 p 的长度。
时间复杂度:O(m * n)

代码:

    public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();// 创建动态规划数组,dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配boolean[][] dp = new boolean[m + 1][n + 1];// 初始化,空字符串和空正则表达式是匹配的dp[0][0] = true;// 处理正则表达式中的 '*',初始化第一行for (int j = 1; j <= n; j++) {if (p.charAt(j - 1) == '*') { // '*' 匹配零个前面的元素dp[0][j] = dp[0][j - 2];}}// 填充动态规划数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {char sc = s.charAt(i - 1);char pc = p.charAt(j - 1);// 如果当前字符匹配,即 '.' 或者与当前字符相同if (pc == '.' || pc == sc) {dp[i][j] = dp[i - 1][j - 1];} else if (pc == '*') {/* 处理 '*' 的情况,分为匹配零个和匹配一个或多个dp[i][j - 2]: 表示 '*' 匹配零个前面的元素,也就是忽略掉 '*' 和它前面的那个字符。(dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')):这部分表示 '*' 匹配一个或多个前面的元素。具体分解如下:dp[i - 1][j]:检查 s 的前 i - 1 个字符和 p 的前 j 个字符是否匹配。(s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'):检查 s 的第 i 个字符和 p 的前 j - 2 个字符是否匹配。*/dp[i][j] = dp[i][j - 2] || (dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.'));}}}// 最终结果为 dp[m][n]return dp[m][n];}

在这里插入图片描述

相关文章:

力扣热门100题刷题笔记 - 10. 正则表达式匹配

力扣热门100题 - 10. 正则表达式匹配 题目链接&#xff1a;10. 正则表达式匹配 题目描述&#xff1a; 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配&#xff…...

4.0 HDFS 配置与使用

之前提到过的 Hadoop 三种模式&#xff1a;单机模式、伪集群模式和集群模式。 单机模式&#xff1a;Hadoop 仅作为库存在&#xff0c;可以在单计算机上执行 MapReduce 任务&#xff0c;仅用于开发者搭建学习和试验环境。 伪集群模式&#xff1a;此模式 Hadoop 将以守护进程的…...

【实训】网络规划与部署实训

一 实训目的及意义 本周实训主要是了解网络规划与部署&#xff0c;熟悉三大厂商华为、思科、锐捷交换机路由器以及相关协议的原理和配置&#xff0c;提高学生的动手能力和分析规划部署能力。 实训主要针对计算机网络系统集成的设计与实现的实际训练&#xff0c;着重锻炼学生熟练…...

相同的树[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你两棵二叉树的根节点p和q&#xff0c;编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同&#xff0c;并且节点具有相同的值&#xff0c;则认为它们是相同的。 示例 1&#xff1a; 输入&#xff1a;p [1,2,3], q [1,…...

02-Web应用_架构构建_漏洞_HTTP数据包_代理服务器

Web应用_架构构建_漏洞_HTTP数据包_代理服务器 一、网站搭建前置知识1.1 域名1.2、子域名1.3、DNS二、web应用环境架构类三、web应用安全漏洞分类四、web请求返回过程数据包 五、演示案例5.1、架构-Web应用搭建-域名源码解析5.2、请求包-新闻回帖点赞-重放数据包5.3、请求包-移…...

使用flink-cdc-sqlserver出现错误,需要批量开启sqlserver表cdc模式,监听表变化

docker安装 docker run -e "ACCEPT_EULAY" -e "MSSQL_SA_PASSWORDZcyc123456" -p 1433:1433 --name sqlserver -d mcr.microsoft.com/mssql/server:2017-latest开启库cdc模式 选择你自己的数据库&#xff0c;执行以下sql语句 EXEC sys.sp_cdc_enable_db…...

ffmpeg的使用,安装,抽帧,加水印,截图,生成gif,格式转换,抓屏等

实际使用中总结的关于ffmpeg对视频的处理的记录文档 具体信息&#xff1a; http://ffmpeg.org/download.html 官网下载ffmpeg 关于ffmpeg的安装详细步骤和说明 装ffmpeg 方式,Linux和windows下的 http://bbs.csdn.net/topics/390519382 php 调用ffmpeg , http://bbs.csdn.net/t…...

游戏视频录制软件推荐,打造专业电竞视频(3款)

随着游戏产业的快速发展&#xff0c;越来越多的玩家开始关注游戏视频录制软件。一款好的录制软件不仅可以帮助玩家记录游戏中的精彩瞬间&#xff0c;还可以让其与他人分享自己的游戏体验。接下来&#xff0c;我们将介绍三款热门的游戏视频录制软件&#xff0c;并对其进行详细的…...

两种方式实现文本超出指定行数显示展开收起...

需要实现这样一个功能 默认高度下文本超出隐藏&#xff0c;点击展开可查看所有内容&#xff0c;点击收起可折叠 方法一&#xff1a;通过html和css实现 代码部分 html:<div className"expand-fold"><input id"check-box" type"checkbox&qu…...

Docker进阶篇-Docker网络

一、描述 1、docker不启动&#xff0c;默认网络情况 查看网卡情况使用&#xff0c;ifconfig或者ip addr ens33&#xff1a;本机网卡 lo&#xff1a;本机回环网络网卡 virbr0:在CentoS 7的安装过程中如果有选择相关虚拟化的的服务安装系统后&#xff0c;启动网卡时会发现 …...

用两个队列实现栈

这里写目录标题 用两个队列实现栈题目描述思路&#xff1a;结构逻辑图如下完整解析代码 用两个队列实现栈 leetcode 题目描述 思路&#xff1a; 准备两个队列&#xff0c;第一个队列依次出队到只剩一个数据时停止&#xff0c;将已出队的数据依次入队到第二个队列&#xff0c;…...

【数据分享】1929-2023年全球站点的逐年降雪深度数据(Shp\Excel\免费获取)

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、能见度等指标&#xff0c;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 之前我们分享过1929-2023年全球气象站点的逐年平均气温数据、逐年最高气温数据…...

Windows11安装运行Linux(Ubuntu)

一、安装windows支持 输入windows打开界面 选择虚拟机监控程序平台、适用于linux的子系统、虚拟机平台 在 Windows 系统中&#xff0c;"虚拟机平台"和"虚拟机监控程序平台"是两个与虚拟化相关的功能&#xff0c;但它们各自有着不同的作用和用途。 虚拟机…...

钉钉群机器人-发送群消息

1、钉钉群创建机器人 添加完成后&#xff0c;要记住 Webhook 路径&#xff1b; 2、机器人接入文档网址 自定义机器人接入 - 钉钉开放平台 3、JAVA代码 import com.dingtalk.api.DefaultDingTalkClient; import com.dingtalk.api.DingTalkClient; import com.dingtalk.api.re…...

OceanBase 4.2.2 GA 发布,全新特性快速预览!

在 2023 年度发布会上&#xff0c;OceanBase 沿着“一体化”产品战略思路&#xff0c;发布了一体化数据库的首个长期支持版本 4.2.1 LTS。作为 4.0 系列的首个 LTS 版本&#xff0c;该版本的定位是支撑客户关键业务稳定长久运行&#xff0c;我们非常认真的打磨了这个版本&#…...

IP代理類型詳解 | 基於網路協議、匿名性、IP來源

線上代理、HTTP代理、Socks4/5代理、動態住宅IP代理、專用代理、共用代理、開放代理、匿名代理、反向代理……是否令你感到困惑&#xff1f;閱讀本片文章瞭解所有。可以將代理視為你與所需網站Web伺服器之間的中間人。它接收你的請求&#xff0c;然後將請求發送到Web伺服器。然…...

uniapp中使用EelementPlus

uniapp的强大是非常震撼的&#xff0c;一套代码可以编写到十几个平台。这个可以在官网上进行查询uni-app官网。主要还是开发小型的软件系统&#xff0c;使用起来非常的方便、快捷、高效。 uniapp中有很多自带的UI&#xff0c;在创建项目的时候&#xff0c;就可以自由选择。而E…...

Swift Vapor 教程(查询数据、插入数据)

上一篇简单写了 怎么创建 Swift Vapor 项目以及在开发过程中使用到的软件。 这一篇写一个怎么在创建的项目中创建一个简单的查询数据和插入数据。 注&#xff1a;数据库配置比较重要 先将本地的Docker启动起来&#xff0c;用Docker管理数据库 将项目自己创建的Todo相关的都删掉…...

QT自用,勿点

自己有接近2年的前端经验&#xff08;html,js,jq,vue之类的&#xff09;&#xff0c;但是一直对QT不是很熟悉&#xff0c;之前零散的学了一些&#xff0c;但是平时不怎么做界面&#xff0c;这几天系统的学一下。 1.7 创建第一个Qt项目_哔哩哔哩_bilibili 文档: *Qt中的信号槽…...

计组学习笔记2024/2/5

记录每天学到了什么,同时在挪移图片过程中再次理解加深印象 学计算机最重要的是理解,而不是整齐的笔记,不要主次搞混,所以以后记笔记的模式也要改一下(主要还是自己太菜,还达不到一边做到整齐笔记的同时还能够有时间做到理解,所以只能舍弃整齐时间保留理解时间)(不过如果有现成…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度

文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

RSS 2025|从说明书学习复杂机器人操作任务:NUS邵林团队提出全新机器人装配技能学习框架Manual2Skill

视觉语言模型&#xff08;Vision-Language Models, VLMs&#xff09;&#xff0c;为真实环境中的机器人操作任务提供了极具潜力的解决方案。 尽管 VLMs 取得了显著进展&#xff0c;机器人仍难以胜任复杂的长时程任务&#xff08;如家具装配&#xff09;&#xff0c;主要受限于人…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

小木的算法日记-多叉树的递归/层序遍历

&#x1f332; 从二叉树到森林&#xff1a;一文彻底搞懂多叉树遍历的艺术 &#x1f680; 引言 你好&#xff0c;未来的算法大神&#xff01; 在数据结构的世界里&#xff0c;“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的&#xff0c;它…...