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

【LeetCode】剑指 Offer 19. 正则表达式匹配 p124 -- Java Version

题目链接:https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/

1. 题目介绍(19. 正则表达式匹配)

请实现一个函数用来匹配包含'. ''*'的正则表达式。模式中的字符'.'表示任意一个字符,而’*'表示它前面的字符可以出现任意次(含0次)。在本题中,匹配是指字符串的所有字符匹配整个模式。例如,字符串"aaa"与模式"a.a""ab*ac*a"匹配,但与"aa.a""ab*a"均不匹配。

【测试用例】:
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:

输入:
s = “ab”
p = “."
输出: true
解释: ".
” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。

示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:
s = “mississippi”
p = “misisp*.”
输出: false

【条件约束】:

提示

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母以及字符 .*,无连续的 '*'

【相似题目】:

  • 【LeetCode】No.10. Regular Expression Matching – Java Version

2. 题解

2.1 递归 – O(2n)

时间复杂度O(2n),空间复杂度O(n)

在这里插入图片描述

class Solution {public boolean isMatch(String s, String p) {if (p.isEmpty()) return s.isEmpty();int sx = 0;int px = 0;return matchCore(s.toCharArray(), sx, p.toCharArray(), px);}public boolean matchCore(char[] str, int sx, char[] pattern, int px) {// 递归终止条件// 1. 同时结束if (sx == str.length && px == pattern.length) {return true;}// 2. pattern先结束if (sx != str.length && px == pattern.length) {return false;}// 当模式中的第二个字符是'*'时if (px + 1 < pattern.length && pattern[px+1] == '*' ){// 且模式的当前字符与字符串中的字符相匹配 or 模式当前字符为'.',可以匹配任意一个字符,if (sx != str.length && (pattern[px] == str[sx] || (pattern[px] == '.'))) {// 如果模式中的第一个字符和字符串中的第一个字符相匹配,下面就有2种选择// 1. 匹配1次或多次,一个一个往后匹配return matchCore(str, sx+1, pattern, px)// 2. 匹配0次,pattern直接跳过两个字符,即忽略"x*"|| matchCore(str, sx, pattern, px+2);} else // 匹配0次,pattern直接跳过两个字符,即忽略"x*"return matchCore(str, sx, pattern, px+2);} // 当模式中的字符是'.'时,或模式中字符不是'.',但仍与字符串中字符相匹配时,接着匹配后面的字符if (sx != str.length && (str[sx] == pattern[px] || pattern[px] == '.'))return matchCore(str, sx+1, pattern, px+1);return false;}
}

在这里插入图片描述

2.2 动态规划 – O(mn)

时间复杂度O(mn),空间复杂度O(mn)
不得不说,动态规划确实快。
在这里插入图片描述
在这里插入图片描述
思路图解:
在这里插入图片描述

class Solution {public boolean isMatch(String s, String p) {int m = s.length() + 1, n = p.length() + 1;boolean[][] dp = new boolean[m][n];// dp[0][0] = true: 代表两个空字符串能够匹配。dp[0][0] = true;// 初始化首行// dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*': 首行 s 为空字符串,因此当 p 的偶数位为 * 时才能够匹配(即让 p 的奇数位出现 0 次,保持 p 是空字符串)for(int j = 2; j < n; j += 2)dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';// 状态转移for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = p.charAt(j - 1) == '*' ?dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));}}return dp[m - 1][n - 1];}
}

在这里插入图片描述

3. 参考资料

[1] 《剑指Offer》Java刷题 NO.52 正则表达式匹配(字符串、正则表达式、递归、动态规划) – 递归代码参考
[2] 剑指 Offer 19. 正则表达式匹配(动态规划,清晰图解)-- 动态规划解法参考

相关文章:

【LeetCode】剑指 Offer 19. 正则表达式匹配 p124 -- Java Version

题目链接&#xff1a;https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/ 1. 题目介绍&#xff08;19. 正则表达式匹配&#xff09; 请实现一个函数用来匹配包含. 和*的正则表达式。模式中的字符.表示任意一个字符&#xff0c;而’*表示它前面的字符可以出现任意…...

linux和windows中安装emqx消息服务器

大家好&#xff0c;我是雄雄&#xff0c;欢迎关注微信公众号雄雄的小课堂 现在是&#xff1a;2023年3月1日21:53:55 前言 最近几天看了下mqtt&#xff0c;通过不断的搜索资料&#xff0c;也将mqtt集成到项目中&#xff0c;跑了个demo运行&#xff0c;和预想中的差不多&#x…...

【XXL-JOB】XXL-JOB的搭建和使用

【XXL-JOB】XXL-JOB的搭建和使用 文章目录【XXL-JOB】XXL-JOB的搭建和使用1. 任务调度1.1 实现任务调度1.1.1 多线程实现1.1.2 Timer实现1.1.3 ScheduledExecutor实现2. 分布式任务调度2.1 采用分布式的原因3. XXL-JOB3.1 XXL-JOB介绍3.2 执行流程4. 搭建XXL-JOB4.1 创建数据库…...

HCIP-5OSPF基本原理及基本配置学习笔记

1、OSPF基本原理 开放式最短路径优先OSPF&#xff08;Open Shortest Path First&#xff09;协议是IETF定义的一种基于链路状态的内部网关路由协议。 RIP是一种基于距离矢量算法的路由协议&#xff0c;存在着收敛慢、易产生路由环路、可扩展性差等问题&#xff0c;目前已逐渐被…...

Migrate your data into databend with DataX

现在互联网应用越来越复杂&#xff0c;每个公司都会有多种多样的数据库。通常是用最好的硬件来跑 OLTP&#xff0c;甚至还在 OLTP 中进行分库分表来满足业务&#xff0c;这样对于一些分析&#xff0c;聚合&#xff0c;排序操作非常麻烦。这也有了异构数据库的数据同步需求&…...

ssh: Permission denied (publickey,gssapi-keyex,gssapi-with-mic,password)

【ansible 设置host为localhost&#xff0c;执行ping命令报错】 [eniq-slocalhost ansible]$ ansible all -m ping -i inventory localhost | UNREACHABLE! > { "changed": false, "msg": "Failed to connect to the host via ssh: Perm…...

有限元中三角形的一些积分公式

文章目录有限元中三角形的相关积分公式有限元中三角形的相关积分公式 在 xyxyxy 平面中&#xff0c; 通过三个点 (xi,yi),(xj,yj),(xm,ym)(x_i, y_i), (x_j, y_j), (x_m, y_m)(xi​,yi​),(xj​,yj​),(xm​,ym​) 定义一个三角形&#xff0c; 令坐标原点位于其中心(或者重心)…...

【docker-compose】安装mongodb

1. 安装方式 压缩包容器安装docker&#xff08;推荐&#xff0c;一分钟安装&#xff09; 2. 环境 linux服务器已安装好 docker docker-compose &#xff08;不了解的客官&#xff0c;请点击进入&#xff09; 3. 步骤&#xff1a; Step 1&#xff1a; linux下建立如下目录…...

【ClickHouse源码】物化视图的写入过程

本文对 ClickHouse 物化视图的写入流程源码做个详细说明&#xff0c;基于 v22.8.14.53-lts 版本。 StorageMaterializedView 首先来看物化视图的构造函数&#xff1a; StorageMaterializedView::StorageMaterializedView(const StorageID & table_id_,ContextPtr local_…...

.NET 使用NLog增强日志输出

引言 不管你是开发单体应用还是微服务应用&#xff0c;在实际的软件的开发、测试和运行阶段&#xff0c;开发者都需要借助日志来定位问题。因此一款好的日志组件将至关重要&#xff0c;在.NET 的开源生态中&#xff0c;目前主要有Serilog、Log4Net和NLog三款优秀的日志组件&…...

一道阿里类的初始化顺序笔试题

问题很简单&#xff0c;就是下面的代码打印出什么&#xff1f; public class InitializeDemo {private static int k 1;private static InitializeDemo t1 new InitializeDemo("t1" );private static InitializeDemo t2 new InitializeDemo("t2");priv…...

cuda找不到路径报错

编译C文件时出现&#xff1a;error: [Errno 2] No such file or directory: :/usr/local/cuda:/usr/local/cuda/bin/nvcc 在终端输入&#xff1a; export CUDA_HOME/usr/local/cuda...

Elasticsearch进阶之(核心概念、系统架构、路由计算、倒排索引、分词、Kibana)

Elasticsearch进阶之&#xff08;核心概念、系统架构、路由计算、倒排索引、分词、Kibana&#xff09; 1、核心概念&#xff1a; 1.1、索引&#xff08;Index&#xff09; 一个索引就是一个拥有几分相似特征的文档的集合。比如说&#xff0c;你可以有一个客户数据的索引&…...

Android包体积缩减

关于减小包体积的方案&#xff1a; 一、所有的图片压缩&#xff0c;采用webp 格式。 &#xff08;当然有些图片采用webp格式反而变大了&#xff0c;可以仍采用png格式&#xff09; 二、语音资源过滤 只保留中文 resConfigs "zh-rCN", "zh” 可以减少resourc…...

【华为OD机试】 网上商城优惠活动(C++ Java Javascript Python)

文章目录 题目描述输入描述输出描述备注用例题目解析C++JavaScriptJavaPython题目描述 某网上商场举办优惠活动,发布了满减、打折、无门槛3种优惠券,分别为: 每满100元优惠10元,无使用数限制,如100199元可以使用1张减10元,200299可使用2张减20元,以此类推;92折券,1次…...

GWT安装过程

1:安装前准备 &#xff08;可以问我要&#xff09; appengine-java-sdk-1.9.8 com.google.gdt.eclipse.suite.4.3.update.site_3.8.0 gwt-2.5.1 eclipse-jee-kepler-SR2-win32-x86_64.zip 2&#xff1a;安装环境上 打开eclipse Help –Install New Software… 选择Add –…...

代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

Leetcode 704 二分查找题目链接&#xff1a;704二分查找介绍给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。思路先看看一个…...

office@word@ppt启用mathtype组件方法整理

文章目录将mathtype添加到word中ref查看office安装路径文件操作法Note附PPT中使用mathtype将mathtype添加到word中 先安装office,再安装mathtype,那么这个过程是自动的如果是先安装mathtype,再安装office,那么有以下选择: 重新安装一遍mathtype(比较简单,不需要说明)执行文件操…...

计算机大小端

我们先假定内存结构为上下型的&#xff0c;上代表内存高地址&#xff0c;下代表内存低地址。 电脑读取内存数据时&#xff0c;是从低位地址到高位地址进行读取&#xff08;从下到上&#xff09;。 1、何为大小端 大端&#xff1a;数据的高位字节存放在低地址&#xff0c;数据…...

Matplotlib绘图从零入门到实践(含各类用法详解)

一、引入 Matplotlib 是一个Python的综合库&#xff0c;用于在 Python 中创建静态、动画和交互式可视化。 本教程包含笔者在使用Matplotlib库过程中遇到的各类完整实例与用法还有遇到的库理论问题&#xff0c;可以根据自己的需要在目录中查询对应的用法、实例以及第四部分关于…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

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

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...