leetcode10 -- 正则表达式匹配
题目描述:
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
示例 1:
输入:s = "aa", p = "a" 输出:false 解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "a*" 输出:true 解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:
输入:s = "ab", p = ".*" 输出:true 解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
提示:
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母,以及字符.和*。- 保证每次出现字符
*时,前面都匹配到有效的字符
解法:
首先理解题目的意思,要判断两个字符串s和p是否匹配,匹配返回true,否则返回false。
.可以代表任意单个字符
*可以代表零个或多个前面的元素
一、先考虑特殊情况
1.p和s均为空串,此时一定匹配。
2.p为空串,s不为空串,一定不匹配。
3.s为空串,但p不为空串,此时需要看p字符串末位是否为‘*’,如果是,则可以使得其左侧的字符出现零次,达到消除效果,如果情况正好可以消除完全,则可以匹配,否则不能匹配。
二、非空情况

这里是大问题包含子问题,要判断s与p是否匹配,那么就需要判断s与p的子串是否能匹配。
从左至右遍历s与p字符串,i表示s串遍历下标,j表示p串遍历下标,针对每个i和j,也就形成了s和p的不同子串。
我们可以s与p每个子串的末尾元素是否匹配,然后判断左侧剩余子串是否匹配。
用dp[i][j]表示s的前i个字符(s下标为0~i-1)与p的前j个字符(p下标为0~j-1)是否匹配,即如果dp[i][j]为true,s的前i个字符与p的前j个字符匹配,反之不匹配。

1.s[i-1]与p[j-1]匹配
那么如果s的第i个字符和p的第j个字符匹配的话,即当s[i-1]=p[j-1](字符相等)或者p[j-1]='.'(.可以替代任意单个字符)时,两个串是否匹配则取决于除末尾位之外的剩余子串是否匹配,即s的前i-1个字符与p的前j-1个字符是否匹配,也就是dp[i][j]=dp[i-1][j-1]。

2.s[i-1]与p[j-1]不匹配
末位不匹配分两种情况:

1)末位字符不等且p[j-1]不是‘*’
这种情况没办法匹配了,能影响字符的只有‘.’和‘*’两个字符,但是*只会影响它左侧的元素,所以如果末位不等,没办法通过转变来使得其匹配。
2)末位字符不等但p[j-1]为‘*’
此时因为‘*’会影响左侧字符,所以需要分情况考虑。
(1)比较p[j-2]与s[i-1]是否匹配,如果匹配有以下几种情况:
p[j-1]为‘*’,那么p[j-2]在匹配过程中受到‘*’影响,出现的次数是不确定的,可能因为匹配而小时,也可能出现1次、2次甚至更多次,因为‘*’可以让其左侧元素出现不确定的数量,只要有某一种情况可以使剩余子串匹配则可行。



(2)如果p[j-2]与s[i-1]不匹配
此时p[j-1]='*',可以使得p[j-2]出现零次而消失,那么就需要比较s[i-1]和p[j-3]是否匹配。
三、整体代码:
class Solution {public boolean isMatch(String s, String p) {char[] cs = s.toCharArray();char[] cp = p.toCharArray();// dp[i][j],s的前i个字符与p的前j个字符是否匹配boolean[][] dp = new boolean[cs.length + 1][cp.length + 1];// s,p均为空dp[0][0] = true;// p空,s不空,false// s空,p不空,分情况(*影响)for (int j = 1; j <= cp.length; j++) {if (cp[j - 1] == '*') {dp[0][j] = dp[0][j - 2];}}for (int i = 1; i <= cs.length; i++) {for (int j = 1; j <= cp.length; j++) {// 文本串和模式串末尾字符匹配if (cs[i - 1] == cp[j - 1] || cp[j - 1] == '.') {dp[i][j] = dp[i - 1][j - 1];} else if (cp[j - 1] == '*') {// p末尾是*// p的*的前一个字符与s末尾能匹配if (cs[i - 1] == cp[j - 2] || cp[j - 2] == '.') {dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];} else {dp[i][j] = dp[i][j - 2];}}}}return dp[cs.length][cp.length];}
}
参考题解:
https://leetcode.cn/problems/regular-expression-matching/solutions/
相关文章:
leetcode10 -- 正则表达式匹配
题目描述: 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符* 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 示例 1࿱…...
Binius-based zkVM:为Polygon AggLayer开发、FPGA加速的zkVM
1. 引言 近日,ZK硬件加速巨头Irreducible和Polygon团队宣布联合开发生产级的Binius-based zkVM,用于助力Polygon AggLayer,实现具有低开销、硬件加速的binary proofs。 Irreducible(曾用名为Ulvetanna)团队 Benjamin …...
基于 HTML+ECharts 实现的大数据可视化平台模板(含源码)
构建大数据可视化平台模板:基于 HTML 和 ECharts 的实现 大数据的可视化对于企业决策、市场分析和业务洞察至关重要。通过直观的数据展示,团队可以快速理解复杂的数据模式,发现潜在的业务机会。本文将详细介绍如何利用 HTML 和 ECharts 实现一…...
特征工程在机器学习中的重要性
特征工程在机器学习中的重要性 特征工程在机器学习中占据着至关重要的地位,它是连接原始数据与机器学习模型之间的桥梁。通过特征工程,我们可以将原始数据转换为机器学习算法能够有效利用的形式,从而提高模型的性能和准确性。以下是特征工程…...
【css】flex布局父元素宽度或高度无法被子元素撑开-bug记录
简言 flex布局父元素宽度或高度无法被子元素撑开问题。 解决方案: 手动计算子元素内容所占宽高,手动赋值给父元素即可。 flex布局宽高度问题 flex布局现在是特别常见得布局方式。 在此记录一个注意点:flex布局在不换行得情况下,…...
Music Tag Editor Pro for Mac:强大的音频标签管理工具
Music Tag Editor Pro for Mac是一款专为Mac系统设计的音频标签管理工具,其简易直观的操作界面和强大的功能深受用户喜爱。 这款软件的核心功能在于它能够批量编辑各类音频文件的标签。无论是修改元数据、重命名文件,还是转换音乐标签的文本编码&#x…...
2024秋招算法
文章目录 参考资料一 数组1.1 二分查找1.2 移除元素1.3 长度最小的子数组1.4 螺旋矩阵1.5 在排序数组中查找元素的第一个和最后一个位置 二 链表2.1 移除链表元素2.2 设计链表2.3 反转链表2.4 两两交换链表中的节点2.5 删除链表的倒数第N个节点2.6 链表相交2.7 环形链表II 三 哈…...
El-Table 表格的表头字段切换
最近写了一个小功能,比较有意思,特此博客记录。 提出需求:需要表头字段变化,但是我在官网上的表格相关上查找,没有发现便捷方法。 于是我有两个想法:1.做三个不同的表格。2.做一个表格使用不同的表头字段。…...
分布式事务 详解
1.简介 2.本地事务失效问题 可以使用AOP starter aspectJ 代理 这样就可以拿到它的上下文的代理对象,当然是有这样的需求才这么做 如果你的事务只是想默认的传播行为,共用上面的事务,就可以不用这个啦 详情请去了解 Raft 算法 还有 pa…...
【git】太大了失败: fatal: fetch-pack: invalid index-pack output
#‘’ Git仓库过大致使clone失败的解决方法 上述大神的方法,亲测有效 中途失败: 太大了 fetch-pack: unexpected disconnect while reading sideband packet fatal: early EOF fatal: fetch-pack: invalid index-pack output关闭压缩 git config --global core.…...
在 ArchLinux 上编译运行 axmol 引擎
本文将在 Windows 10 上安装 Arch WSL 中编译 axmol 请确保 WSL2 已正确安装 1. 在微软应用商店安装 ArchLinux 2. 打开 Arch,按照提示输入用户名和密码,尽量简单 3. 配置清华源,速度快的起飞,否则,各种包会安装失败…...
云计算的三种服务模式
云计算的三种主要服务模式分别是基础设施即服务(IaaS)、平台即服务(PaaS)和软件即服务(SaaS)。每种服务模式都提供不同级别的抽象和管理,满足不同的需求和用例。以下是对这三种服务模式的详细介…...
Pytorch使用教学1-Tensor的创建
0 导读 在我们不知道什么是深度学习计算框架时,我们可以把PyTorch看做是Python的第三方库,在PyTorch中定义了适用于深度学习的张量Tensor,以及张量的各类计算。就相当于NumPy中定义的Array和对应的科学计算方法,正是这些基本数据…...
R语言统计分析——数据管理4
参考资料:R语言实战【第2版】 1、数学函数 abs(x):绝对值 sqrt(x):平方根 ceiling(x):不小于x的最小整数 floor(x):不大于x的最大整数 trunc(x):向0的方向截取x中的整数部分 round(x,digitsn)&#…...
用uniapp 及socket.io做一个简单聊天app 2
在这里只有群聊,二个好友聊天,可以认为是建了一个二人的群聊。 const express require(express); const http require(http); const socketIo require(socket.io); const cors require(cors); // 引入 cors 中间件const app express(); const serv…...
Si24R03:高度集成的低功耗SOC芯片中文资料
Si24R03是一款高度集成的低功耗SOC芯片,具有低功耗、Low Pin Count、宽电压工作范围,集成了13/14/15/16位精度的 ADC、LVD、UART、SPI、I2C、TIMER、WUP、IWDG、RTC、无线收发器等丰富的外设。 合封说明:Si24R03为CSM32RV003和Si24R1的合封芯…...
K8s-控制器
一 为什么使用控制器 pod控制器 作用:1.pod类型资源删除,不会重建 2.控制器可以帮助用户监控,并保证节点上运行定义好的pod副本数 3.pod超过或低于用户期望,控制器会创建、删除pod副本数量 控制器类型&am…...
Meta 发布 LLAMA 3.1;特斯拉无人出租车推迟至 10 月;谷歌将向 Waymo 再投 50 亿美元
先瞧一下 Chat 和 Agent 的差异。 Chat(聊天):纯粹的 Chat,宛如一个主要由“大脑与嘴”组成的智能体,着重于信息处置和语言沟通。诸如 ChatGPT 这般的系统,其能够领会用户的询问,给出有益且连贯…...
C 语言基础概念总结
C 语言基础概念总结 一、数据类型 目录 C 语言基础概念总结 一、数据类型 基本数据类型 构造数据类型 二、变量与常量 三、运算符与表达式 算术运算符 关系运算符 逻辑运算符 赋值运算符 自增自减运算符 四、控制流语句 顺序结构 选择结构 循环结构 五、函数 …...
Django教程(000):初识Django
Django 是一个高级 Python Web 框架,旨在快速开发、简洁、实用。Django 提供了众多内置功能,使得开发者可以专注于编写应用程序的业务逻辑,而不需要过多关注底层细节。以下是 Django 的详细介绍: 1. Django 简介 Django 是一个开放源代码的 Web 框架,由 Python 编写,最…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
