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

leetCode算法—10. 正则表达式匹配

10.给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

难度:困难 ***
给你一个字符串 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 的小写字母,以及字符 . 和 *。
    保证每次出现字符 * 时,前面都匹配到有效的字符

解法

const isMatch = (s, p) => {if (s == null || p == null) return false;const sLen = s.length, pLen = p.length;const dp = new Array(sLen + 1);for (let i = 0; i < dp.length; i++) {dp[i] = new Array(pLen + 1).fill(false); // 将项默认为false}// base casedp[0][0] = true;for (let j = 1; j < pLen + 1; j++) {if (p[j - 1] == "*") dp[0][j] = dp[0][j - 2];}// 迭代for (let i = 1; i < sLen + 1; i++) {for (let j = 1; j < pLen + 1; j++) {if (s[i - 1] == p[j - 1] || p[j - 1] == ".") {dp[i][j] = dp[i - 1][j - 1];} else if (p[j - 1] == "*") {if (s[i - 1] == p[j - 2] || p[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[sLen][pLen]; // 长sLen的s串 是否匹配 长pLen的p串
};

上一篇:leetCode算法—9. 回文数
下一篇:leetCode算法—11. 盛最多水的容器

相关文章:

leetCode算法—10. 正则表达式匹配

10.给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 难度&#xff1a;困难 *** 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹…...

Android Studio 实现音乐播放器

目录 一、引言 视频效果展示&#xff1a; 1.启动页效果 2.登录页效果 3.注册页效果 4.歌曲列表页效果 5.播放页效果 二、详细设计 1.登陆注册功能 2.音乐列表页面 2.音乐播放功能 三、源码获取 一、引言 Android初学者开发第一个完整的实例项目应该就属《音乐播放器…...

端口占用命令 netstat (centos)+netstat (windows)

linux 1.使用 netstat 命令查看端口占用情况 netstat -tlnp 使用 -p 选项查看进程信息。 使用 -t 选项列出 TCP 协议的连接&#xff1a;类似&#xff08;使用 -u 选项列出 UDP 协议的连接&#xff1a;&#xff09; 2.查找占用指定端口号的应用信息 netstat -tlnp | grep 3…...

Python-基于fastapi实现SSE流式返回(类似GPT)

最近在做大模型对话相关功能&#xff0c;需要将对话内容流式返回给前端页面&#xff08;类似GPT的效果&#xff09;。下面直接说下如何实现&#xff1a; 1.首先导入fastapi和sse流式返回所需要的包 from fastapi import APIRouter, Response, status from sse_starlette.sse …...

iOS中宿主APP与录屏扩展进程数据传递方式

背景 在iOS生态系统中&#xff0c;应用程序的功能不再局限于单一的宿主应用&#xff0c;而是可以通过扩展进程实现更丰富的用户体验和功能。其中一种引人注目的扩展是录屏功能&#xff0c;它使用户能够捕捉设备屏幕上的活动&#xff0c;无论是游戏过程、教育演示还是其他应用场…...

Windows系统下的可用RADIUS软件-[资源]

RADIUS协议相关原理介绍&#xff0c;可参考博客RADIUS协议原理介绍报文分析配置指导-RFC2865/RFC2866。 本文用于提供和介绍Window系统下几种可用的RADIUS软件。主要涉及软件有radius_ping&#xff08;绿色免安装版&#xff09;和WinRadius&#xff08;绿色免安装版&#xff09…...

基于VUE3+Layui从头搭建通用后台管理系统(前端篇)十五:基础数据模块相关功能实现

一、本章内容 本章使用已实现的公共组件实现系统管理中的基础数据中的验证码管理、消息管理等功能。 1. 详细课程地址: 待发布 2. 源码下载地址: 待发布 二、界面预览 三、开发视频 3.1 B站视频地址: 基于VUE3+Layui从头搭建通用后台管理系统合集-验证码功能实现 3.2 西瓜…...

MAC苹果笔记本电脑如何彻底清理垃圾文件软件?

苹果电脑以其流畅的操作系统和卓越的性能而备受用户喜爱。然而&#xff0c;随着时间的推移&#xff0c;系统可能会积累大量垃圾文件&#xff0c;影响性能。本文将介绍苹果电脑怎么清理垃圾文件的各种方法&#xff0c;以提升系统运行效率。 CleanMyMac X是一款专业的Mac清理软件…...

【Linux C | 文件I/O】文件的打开关闭 | open、creat、colse 函数

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

【BEV感知】BEVFormer 融合多视角图形的空间特征和时序特征 ECCV 2022

前言 本文分享BEV感知方案中&#xff0c;具有代表性的方法&#xff1a;BEVFormer。 它基于Deformable Attention&#xff0c;实现了一种融合多视角相机空间特征和时序特征的端到端框架&#xff0c;适用于多种自动驾驶感知任务。 主要由3个关键模块组成&#xff1a; BEV Que…...

Amazon Toolkit — CodeWhisperer 使用

tFragment--> 官网&#xff1a;https://aws.amazon.com/cn/codewhisperer/?trkcndc-detail 最近学习了亚马逊云科技的 代码工具&#xff0c;感慨颇多。下面是安装 和使用的分享。 CodeWhisperer&#xff0c;亚马逊推出的实时 AI 编程助手&#xff0c;是一项基于机器学习…...

Flink SQL填坑记2:Flink和MySQL的Bigdata类型不同导致ClassCastException报错

最近在开发Flink SQL的时候,需要关联Kafka事实表和MySQL维表,得到的数据写入Phoenix表中,但是其中有个字段,Kafka表、MySQL表和Phoenix表都是BigData类型,但是在实现的时候却报“java.math.BigInteger cannot be cast to java.lang.Long”异常,从报错信息来看,是由于Big…...

本地MinIO存储服务如何创建Buckets并实现公网访问上传文件

文章目录 前言1. 创建Buckets和Access Keys2. Linux 安装Cpolar3. 创建连接MinIO服务公网地址4. 远程调用MinIO服务小结5. 固定连接TCP公网地址6. 固定地址连接测试 前言 MinIO是一款高性能、分布式的对象存储系统&#xff0c;它可以100%的运行在标准硬件上&#xff0c;即X86等…...

通过https协议访问Tomcat部署并使用Shiro认证的应用跳转登到录页时协议变为http的问题

问题描述&#xff1a; 在最近的一个项目中&#xff0c;有一个存在较久&#xff0c;并且只在内部城域网可访问的一个使用Shiro框架进行安全管理的Java应用&#xff0c;该应用部署在Tomcat服务器上。起初&#xff0c;应用程序可以通过HTTP协议访问&#xff0c;一切运行都没…...

Backend - Django 项目创建 运行

目录 一、配置环境 二、创建 Django 项目 &#xff08;一&#xff09;新建文件夹 &#xff08;二&#xff09;打开文件夹 &#xff08;三&#xff09;打开运行终端 &#xff08;四&#xff09;创建基础项目 &#xff08;五&#xff09;创建app 1. 安装Django &#xf…...

C# .Net学习笔记—— Expression 表达式目录树

一、什么是表达式目录树 &#xff08;1&#xff09;Expression我们称为是表达式树&#xff0c;是一种数据结构体&#xff0c;用于存储需要计算&#xff0c;运算的一种结构&#xff0c;这种结构可以只是存储&#xff0c;而不进行运算。通常表达式目录树是配合Lambda一起来使用的…...

《论文阅读28》Unsupervised 3D Shape Completion through GAN Inversion

GAN&#xff0c;全称GenerativeAdversarialNetworks&#xff0c;中文叫生成式对抗网络。顾名思义GAN分为两个模块&#xff0c;生成网络以及判别网络&#xff0c;其中 生成网络负责根据随机向量产生图片、语音等内容&#xff0c;产生的内容是数据集中没有见过的&#xff0c;也可…...

一个正则快速找到在ES中使用profile的时产生慢查询的分片

在es中使用profile分析慢查询的时候&#xff0c;往往因为分片过多&#xff0c;或者因为查询条件太复杂&#xff0c;分析的结果几十万行。在kibana上点半天&#xff0c;也找不到一个耗时长的分片。 kibana上可以通过正则来匹配。其实我们只需要匹配到耗时大于10秒的请求。 检索语…...

链接未来:深入理解链表数据结构(一.c语言实现无头单向非循环链表)

在上一篇文章中&#xff0c;我们探索了顺序表这一基础的数据结构&#xff0c;它提供了一种有序存储数据的方法&#xff0c;使得数据的访 问和操作变得更加高效。想要进一步了解&#xff0c;大家可以移步于上一篇文章&#xff1a;探索顺序表&#xff1a;数据结构中的秩序之美 今…...

Python tkinter控件全集之组合选择框 ttk.ComboBox

Tkinter标准库 Tkinter是Python的标准GUI库&#xff0c;也是最常用的Python GUI库之一&#xff0c;提供了丰富的组件和功能&#xff0c;包括窗口、按钮、标签、文本框、列表框、滚动条、画布、菜单等&#xff0c;方便开发者进行图形界面的开发。Tkinter库基于Tk for Unix/Wind…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...