力扣热门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. 正则表达式匹配 题目链接:10. 正则表达式匹配 题目描述: 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配ÿ…...
4.0 HDFS 配置与使用
之前提到过的 Hadoop 三种模式:单机模式、伪集群模式和集群模式。 单机模式:Hadoop 仅作为库存在,可以在单计算机上执行 MapReduce 任务,仅用于开发者搭建学习和试验环境。 伪集群模式:此模式 Hadoop 将以守护进程的…...
【实训】网络规划与部署实训
一 实训目的及意义 本周实训主要是了解网络规划与部署,熟悉三大厂商华为、思科、锐捷交换机路由器以及相关协议的原理和配置,提高学生的动手能力和分析规划部署能力。 实训主要针对计算机网络系统集成的设计与实现的实际训练,着重锻炼学生熟练…...
相同的树[简单]
优质博文:IT-BLOG-CN 一、题目 给你两棵二叉树的根节点p和q,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。 示例 1: 输入: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模式 选择你自己的数据库,执行以下sql语句 EXEC sys.sp_cdc_enable_db…...
ffmpeg的使用,安装,抽帧,加水印,截图,生成gif,格式转换,抓屏等
实际使用中总结的关于ffmpeg对视频的处理的记录文档 具体信息: http://ffmpeg.org/download.html 官网下载ffmpeg 关于ffmpeg的安装详细步骤和说明 装ffmpeg 方式,Linux和windows下的 http://bbs.csdn.net/topics/390519382 php 调用ffmpeg , http://bbs.csdn.net/t…...
游戏视频录制软件推荐,打造专业电竞视频(3款)
随着游戏产业的快速发展,越来越多的玩家开始关注游戏视频录制软件。一款好的录制软件不仅可以帮助玩家记录游戏中的精彩瞬间,还可以让其与他人分享自己的游戏体验。接下来,我们将介绍三款热门的游戏视频录制软件,并对其进行详细的…...
两种方式实现文本超出指定行数显示展开收起...
需要实现这样一个功能 默认高度下文本超出隐藏,点击展开可查看所有内容,点击收起可折叠 方法一:通过html和css实现 代码部分 html:<div className"expand-fold"><input id"check-box" type"checkbox&qu…...
Docker进阶篇-Docker网络
一、描述 1、docker不启动,默认网络情况 查看网卡情况使用,ifconfig或者ip addr ens33:本机网卡 lo:本机回环网络网卡 virbr0:在CentoS 7的安装过程中如果有选择相关虚拟化的的服务安装系统后,启动网卡时会发现 …...
用两个队列实现栈
这里写目录标题 用两个队列实现栈题目描述思路:结构逻辑图如下完整解析代码 用两个队列实现栈 leetcode 题目描述 思路: 准备两个队列,第一个队列依次出队到只剩一个数据时停止,将已出队的数据依次入队到第二个队列,…...
【数据分享】1929-2023年全球站点的逐年降雪深度数据(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、能见度等指标,说到气象数据,最详细的气象数据是具体到气象监测站点的数据! 之前我们分享过1929-2023年全球气象站点的逐年平均气温数据、逐年最高气温数据…...
Windows11安装运行Linux(Ubuntu)
一、安装windows支持 输入windows打开界面 选择虚拟机监控程序平台、适用于linux的子系统、虚拟机平台 在 Windows 系统中,"虚拟机平台"和"虚拟机监控程序平台"是两个与虚拟化相关的功能,但它们各自有着不同的作用和用途。 虚拟机…...
钉钉群机器人-发送群消息
1、钉钉群创建机器人 添加完成后,要记住 Webhook 路径; 2、机器人接入文档网址 自定义机器人接入 - 钉钉开放平台 3、JAVA代码 import com.dingtalk.api.DefaultDingTalkClient; import com.dingtalk.api.DingTalkClient; import com.dingtalk.api.re…...
OceanBase 4.2.2 GA 发布,全新特性快速预览!
在 2023 年度发布会上,OceanBase 沿着“一体化”产品战略思路,发布了一体化数据库的首个长期支持版本 4.2.1 LTS。作为 4.0 系列的首个 LTS 版本,该版本的定位是支撑客户关键业务稳定长久运行,我们非常认真的打磨了这个版本&#…...
IP代理類型詳解 | 基於網路協議、匿名性、IP來源
線上代理、HTTP代理、Socks4/5代理、動態住宅IP代理、專用代理、共用代理、開放代理、匿名代理、反向代理……是否令你感到困惑?閱讀本片文章瞭解所有。可以將代理視為你與所需網站Web伺服器之間的中間人。它接收你的請求,然後將請求發送到Web伺服器。然…...
uniapp中使用EelementPlus
uniapp的强大是非常震撼的,一套代码可以编写到十几个平台。这个可以在官网上进行查询uni-app官网。主要还是开发小型的软件系统,使用起来非常的方便、快捷、高效。 uniapp中有很多自带的UI,在创建项目的时候,就可以自由选择。而E…...
Swift Vapor 教程(查询数据、插入数据)
上一篇简单写了 怎么创建 Swift Vapor 项目以及在开发过程中使用到的软件。 这一篇写一个怎么在创建的项目中创建一个简单的查询数据和插入数据。 注:数据库配置比较重要 先将本地的Docker启动起来,用Docker管理数据库 将项目自己创建的Todo相关的都删掉…...
QT自用,勿点
自己有接近2年的前端经验(html,js,jq,vue之类的),但是一直对QT不是很熟悉,之前零散的学了一些,但是平时不怎么做界面,这几天系统的学一下。 1.7 创建第一个Qt项目_哔哩哔哩_bilibili 文档: *Qt中的信号槽…...
计组学习笔记2024/2/5
记录每天学到了什么,同时在挪移图片过程中再次理解加深印象 学计算机最重要的是理解,而不是整齐的笔记,不要主次搞混,所以以后记笔记的模式也要改一下(主要还是自己太菜,还达不到一边做到整齐笔记的同时还能够有时间做到理解,所以只能舍弃整齐时间保留理解时间)(不过如果有现成…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
ArcPy扩展模块的使用(3)
管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如,可以更新、修复或替换图层数据源,修改图层的符号系统,甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...
结构化文件管理实战:实现目录自动创建与归类
手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题,进而引发后续程序异常。使用工具进行标准化操作,能有效降低出错概率。 需要快速整理大量文件的技术用户而言,这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB,…...
