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

【动态规划】LeetCode-10. 正则表达式匹配

10. 正则表达式匹配。

给你一个字符串 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 <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符
算法分析

解题思路
dp
image
image

class Solution {public boolean isMatch(String s, String p) {int n = s.length(), m = p.length();s = " " + s;p = " " + p;boolean[][] f = new boolean[n + 1][m + 1];f[0][0] = true;for (int i = 0; i <= n; i++) {for (int j = 1; j <= m; j++) {if (p.charAt(j) != '*') {f[i][j] = i != 0 && f[i - 1][j - 1] && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');} else {f[i][j] = f[i][j - 2] || (i != 0 && f[i - 1][j] && (s.charAt(i) == p.charAt(j - 1) || p.charAt(j - 1) == '.'));}}}return f[n][m];}
}

复杂性分析

时间复杂度:O(mn)
空间复杂度:O(mn)

相关文章:

【动态规划】LeetCode-10. 正则表达式匹配

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

lenovo联想拯救者8.8英寸掌上游戏机Legion Go 8APU1(83E1)原装出厂Windows11预装系统

链接&#xff1a;https://pan.baidu.com/s/1d586XWXcAWVxlLyV2Oku7Q?pwdd74t 提取码&#xff1a;d74t 系统自带所有驱动、出厂主题壁纸、Office办公软件、联想电脑管家等预装程序 所需要工具&#xff1a;16G或以上的U盘 文件格式&#xff1a;ISO 文件大小&#xff1a;…...

经典目标检测YOLO系列(一)复现YOLOV1(4)VOC2007数据集的读取及预处理

经典目标检测YOLO系列(一)复现YOLOV1(4)VOC2007数据集的读取及预处理 之前&#xff0c;我们依据《YOLO目标检测》(ISBN:9787115627094)一书&#xff0c;提出了新的YOLOV1架构&#xff0c;并解决前向推理过程中的两个问题&#xff0c;继续按照此书进行YOLOV1的复现。 经典目标检…...

Android Studio xml布局代码补全功能失效问题

这里写目录标题 前言&#xff1a;问题描述原因分析&#xff1a;解决方案&#xff1a;1.更新 Android Studio 版本2.原版本解决XML补全失效 小结 前言&#xff1a; 在开发过程中&#xff0c;你可能遇到很多奇奇怪怪的问题。Android Studio 编译器出现问题也是常有的事情&#x…...

算法每日一题:队列中可以看到的人数 | 单调栈

大家好&#xff0c;我是星恒 今天是一道困难题&#xff0c;他的题解比较好理解&#xff0c;但是不好想出来&#xff0c;接下来就让我带大家来捋一捋这道题的思路&#xff0c;以及他有什么特征 题目&#xff1a;leetcode 1944有 n 个人排成一个队列&#xff0c;从左到右 编号为 …...

报表控件Stimulsoft 2023回顾:都做了哪些产品的改变?

在2023年过去一年中&#xff0c;报表控件Stimulsoft 针各类控件都做了重大改变&#xff0c;其中新增了某些产品、同时加强了很多产品的性能和UI设计&#xff0c;更加符合开发者需求&#xff0c;下面就跟随小编一起来回顾&#xff0c;具体都有哪些↓↓↓ Stimulsoft Ultimate &…...

Mybatis缓存实现方式

文章目录 装饰器模式Cache 接口及核心实现Cache 接口装饰器1. BlockingCache2. FifoCache3. LruCache4. SoftCache5. WeakCache 小结 缓存是优化数据库性能的常用手段之一&#xff0c;我们在实践中经常使用的是 Memcached、Redis 等外部缓存组件&#xff0c;很多持久化框架提供…...

C#用StringBuilder高效处理字符串

目录 一、背景 二、使用StringBuilder便捷、高效地操作字符串 三、实例 1.源码 2.生成效果 四、实例中知识点 1.StringBuilder 构造函数 &#xff08;1&#xff09;定义 &#xff08;2&#xff09;重载 &#xff08;3&#xff09;StringBuilder() &#xff08;4&…...

python开发案例教程-清华大学出版社(张基温)答案(4.2)

目录 练习 4.2 1. 代码分析题 2. 程序设计题 练习 4.2 1. 代码分析题 阅读下面的代码&#xff0c;给出输出结果。 &#xff08;1&#xff09; class A:def __init__(self,a,b,c):self.xabca A(3,5,7);b getattr(a,x);setattr(a,x,b3);print(a.x)18 &#xff08;2&…...

【MATLAB】【数字信号处理】线性卷积和抽样定理

已知有限长序列&#xff1a;xk1,2,1,1,0,-3, hk[1,-1,1] , 计算离散卷积和ykxk*h(k) 。 程序如下&#xff1a; function [t,x] My_conv(x1,x2,t1,t2,dt) %文件名与函数名对应 %自写的卷积函数 x conv(x1,x2)*dt; t0 t1(1) t2(1); L length(x1) length(x2)-2; t t0:dt…...

什么是 MVVM ?

课堂笔记 什么是 MVVM &#xff1f; MVVM 是一种架构模式&#xff0c;它最初是由微软的两位工程师在 2005 年的时候所提出的。 Model&#xff1a;Model代表的是你的数据View&#xff1a;视图&#xff0c;直接和用户打交道的ViewModel&#xff1a;ViewModel 是 View 和 Model…...

Redis(一)

1、redis Redis是一个完全开源免费的高性能&#xff08;NOSQL&#xff09;的key-value数据库。它遵守BSD协议&#xff0c;使用ANSI C语言编写&#xff0c;并支持网络和持久化。Redis拥有极高的性能&#xff0c;每秒可以进行11万次的读取操作和8.1万次的写入操作。它支持丰富的数…...

自动驾驶预测-决策-规划-控制学习(1):自动驾驶框架、硬件、软件概述

文章目录 前言&#xff1a;无人驾驶分级一、不同level的无人驾驶实例分析1.L2级别2.L3级别3.L4级别①如何在减少成本的情况下&#xff0c;实现类似全方位高精度的感知呢&#xff1f;②路侧终归是辅助&#xff0c;主车的智能才是重中之重&#xff1a;融合深度学习 二、无人驾驶的…...

SSM建材商城网站----计算机毕业设计

项目介绍 本项目分为前后台&#xff0c;前台为普通用户登录&#xff0c;后台为管理员登录&#xff1b; 管理员角色包含以下功能&#xff1a; 管理员登录,管理员管理,注册用户管理,新闻公告管理,建材类型管理,配货点管理,建材商品管理,建材订单管理,建材评价管理等功能。 用…...

js逆向第9例:猿人学第2题-js混淆-动态cookie1

题目2:提取全部5页发布日热度的值,计算所有值的加和,并提交答案 (感谢蔡老板为本题提供混淆方案) 既然题目已经给出了cookie问题,那就从cookie入手,控制台找到数据请求地址 可以看到如下加密字符串m类似md5,后面跟着时间戳 m=45cc41dcdb15159ebb50564635f8e362|1704301…...

[论文分享]TimesURL:通用时间序列表示学习的自监督对比学习

论文题目&#xff1a;TimesURL: Self-supervised Contrastive Learning for Universal Time Series Representation Learning 论文地址&#xff1a;https://arxiv.org/abs/2312.15709 代码地址&#xff1a;暂无 摘要 学习适用于各种下游任务的通用时间序列表示具有挑战性&…...

解决sublime中文符号乱码问题

效果图 原来 后来 问题不是出自encode文件编码&#xff0c;而是win10的字体问题。 解决方法 配置&#xff1a; { "font_face":"Microsoft Yahei", "dpi_scale": 1.0 } 参考自 Sublime 输入中文显示方框问号乱码_sublime中文问号-CSDN博…...

厚积薄发11年,鸿蒙究竟有多可怕

​12月20日中国工程院等权威单位发布《2023年全球十大工程成就》。本次发布的2023全球十大工程成就包括“鸿蒙操作系统”在内。入围的“全球十大工程成就”&#xff0c;主要指过去五年由世界各国工程科技工作者合作或单独完成且实践验证有效的&#xff0c;并且已经产生全球影响…...

pyDAL一个python的ORM(4) pyDAL查询操作

1 、简单查询 rows db(db.person.dept marketing).select(db.person.id, db.person.name, db.person.dept) rows db(db.person.dept marketing).select() rows db(db.person.dept marketing).select(db.person.ALL) rows db().select(db.person.ALL) / db(db.person).se…...

如何通过Python将各种数据写入到Excel工作表

在数据处理和报告生成等工作中&#xff0c;Excel表格是一种常见且广泛使用的工具。然而&#xff0c;手动将大量数据输入到Excel表格中既费时又容易出错。为了提高效率并减少错误&#xff0c;使用Python编程语言来自动化数据写入Excel表格是一个明智的选择。Python作为一种简单易…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

在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…...