leetCode第十题 : 正则表达式匹配 动态规划【10/1000 python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作icon-default.png?t=N7T8http://t.csdnimg.cn/Q59WX
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

题目描述

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

解题思路

方法一:递归

递归方法是理解这个问题的一个很好的起点,它可以直观地将问题分解为更小的子问题来解决。

解题步骤

1. 基本情况:如果模式 p 为空,成功匹配取决于字符串 s 也为空。

2. 匹配第一个字符:检查 sp 的第一个字符是否匹配(考虑到 '.')。

3. 使用 '*':如果 p 的第二个字符是 '*',则有两种情况:

  • 我们跳过 '*' 和它之前的字符,因为 '*' 可以匹配零个字符;
  • 如果第一个字符匹配,移动字符串 s,因为 '*' 可以匹配多个字符。

4. 递归匹配剩余字符串:根据以上逻辑递归地匹配剩余的 sp

python示例
def isMatch(s: str, p: str) -> bool:
    # 如果模式为空,成功匹配取决于字符串也为空
    if not p:
        return not s

    # 检查s的第一个字符是否与p的第一个字符匹配
    first_match = bool(s) and p[0] in {s[0], '.'}

    # 如果p的长度大于1并且p的第二个字符是'*'
    if len(p) >= 2 and p[1] == '*':
        # 使用'*'匹配0个字符,或者第一个字符匹配且s向前移动一位
        return (isMatch(s, p[2:])) or first_match and isMatch(s[1:], p)
    else:
        # 如果没有'*',则直接移动s和p都向前移动一位
        return first_match and isMatch(s[1:], p[1:])

# 示例测试
print(isMatch("aa", "a*"))  # True
print(isMatch("mississippi", "mis*is*p*."))  # False

方法二:动态规划

动态规划是解决这个问题的关键方法,它可以有效地避免重复计算,并且处理复杂的 '*' 匹配规则。

解题步骤

1. 初始化DP表:创建一个 (len(s) + 1) x (len(p) + 1) 大小的二维列表 dpdp[i][j] 表示字符串 s 的前 i 个字符与模式 p 的前 j 个字符是否能够匹配。初始化所有元素为 False

2. 基础情况:空字符串和空模式是匹配的,因此 dp[0][0] = True。然后初始化模式 p 中连续的 '*' 对应的状态,因为 '*' 可以取消前一个字符

3. 填充DP表:遍历 sp,对每一对字符更新 dp[i][j]

  • 如果 p[j-1]'*',则有两种情况:
    • '*' 取消前一个字符(即模式 p 跳过两个字符),这时 dp[i][j] 取决于 dp[i][j-2]
    • 使用 '*' 匹配 s 中的多个字符,这时如果 s[i-1]p[j-2] 匹配,dp[i][j] 取决于 dp[i-1][j]
  • 如果 p[j-1]'.' 或者 s[i-1]p[j-1] 相等,dp[i][j] 取决于 dp[i-1][j-1]

4. 返回结果:表格的最后一个元素 dp[-1][-1] 表示整个字符串 s 与模式 p 是否匹配。

python示例
def isMatch(s: str, p: str) -> bool:
    # 初始化DP表,dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
    dp = [[False] * (len(p) + 1) for _ in range(len(s) + 1)]

    # 空字符串与空模式是匹配的
    dp[0][0] = True

    # 处理模式p的前缀为'*'的情况
    for j in range(1, len(p) + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-2]

    # 填充DP表
    for i in range(1, len(s) + 1):
        for j in range(1, len(p) + 1):
            # 当前模式字符为'*'
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))
            # 当前模式字符为'.'或者与字符串字符相同
            else:
                dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == '.')

    return dp[-1][-1]
优缺点
  • 优点
    • 动态规划避免了重复计算,大大提高了效率;
    • 明确地定义了所有状态转移情况,使得算法具有良好的结构性和可读性。
  • 缺点
    • 动态规划的空间复杂度较高,特别是当 sp 长度较大时;
    • 对于初学者来说,理解动态规划的状态转移可能稍显复杂。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/533204.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

软考120-上午题-【软件工程】-软件开发模型02

一、演化模型 软件类似于其他复杂的系统&#xff0c;会随着时间的推移而演化。在开发过程中&#xff0c;常常会面临以下情形&#xff1a;商业和产品需求经常发生变化&#xff0c;直接导致最终产品难以实现&#xff1b;严格的交付时间使得开发团队不可能圆满地完成软件产品&…

Docker安装nacos教程

目录 1.首先拉取nacos镜像2.启动容器&#xff0c;3.查看容器id4.复制容器内的 /home/nacos目录下的logs,data,conf目录到容器外&#xff08;docker cp 后的容器id可以缩略写前几位&#xff09;5.进入上一步操作的conf目录&#xff0c;修改目录下的application.properties的文件…

FORM的引入与使用

FORM的引入与使用 【0】引入 ​ 表单&#xff08;Form&#xff09;是网页中用于收集用户输入数据的一种交互元素。通过表单&#xff0c;用户可以输入文本、选择选项、上传文件等操作。表单通常由一个或多个输入字段&#xff08;Input Field&#xff09;组成&#xff0c;每个字…

【重磅推荐】2024七大零售行业线下开店超全指南大全共452份

如需下载完整PPTX可编辑源文件&#xff0c;请前往星球获取&#xff1a;https://t.zsxq.com/19F4dDDrv 联华快客便利店的加盟手册.docx 好德便利店加盟手册.docx 超市&便利店守则:商品退换货管理.docx 赠品管理制度.doc 选址必看.doc 新人续签考核作业.doc 物流箱管理制度.d…

第04章 计算机常用通信指标和术语视频课程

4.1 本章目标 掌握bit、Byte、KB、MB、GB、TB概念和换算关系掌握波特率、比特率、误码率的概念掌握信道、基带信号、频带信号概念了解多路复用、频分多路复用、时分多路复用了解同步传输、异步传输概念 4.2 bit、Byte、KB、MB、GB、TB概念和换算关系 4.2.1 概念与换算 4.2.2…

SinoDB备份恢复工具之dbexport/dbimport

dbexport和 dbimport是两个简单的备份恢复实用程序&#xff0c;无需任何提前配置即可运行。这两个实用程序可以在不同平台的SinoDB数据库服务器之间迁移数据&#xff0c;可以使用它们备份和还原小型数据库。 1. dbexport命令语法 dbexport以文本格式导出数据库中所有对象的模式…

ENSP防火墙配置VRRP负载分担[图片配置步骤],VRRP简介

配置目标 1.实现同一区域设备分别走两条线路进行通信 2.当一侧线路故障时切换至备份线路 拓扑搭建 配置接口地址及安全区域 fw1&#xff1a; fw2&#xff1a; 配置安全策略 fw1/fw2 配置默认路由 fw1&#xff1a; fw2&#xff1a; 配置IP-link fw1 fw2 配置vrrp FW1&am…

OpenHarmony开发技术:【国际化】实例

国际化 如今越来的越多的应用都走向了海外&#xff0c;应用走向海外需要支持不同国家的语言&#xff0c;这就意味着应用资源文件需要支持不同语言环境下的显示。本节就介绍一下设备语言环境变更后&#xff0c;如何让应用支持多语言。 应用支持多语言 ArkUI开发框架对多语言的…

机器学习和深度学习-- 李宏毅(笔记与个人理解)Day8

Day 8 classification &#xff1a;Probabilistic Generative Model 今天上了一整天的课&#xff0c; 本来实在是更新不动了&#xff0c;但是看到《剑来》更新了&#xff0c;想一想这本书里面一直强调的成功的feature – 心性&#xff0c;嗯心性坚毅就好&#xff01;主人公陈平…

实战项目——智慧社区(二)之 物业管理

分页 用于分页封装的实体类 Data public class PageVO {private Long totalCount;private Long pageSize;private Long totalPage;private Long currPage;private List list; }分页的相关配置 package com.qcby.community.configuration;import com.baomidou.mybatisplus.e…

乡村智慧化升级:数字乡村打造农村生活新品质

目录 一、乡村智慧化升级的内涵与意义 二、乡村智慧化升级的具体实践 1、加强农村信息基础设施建设 2、推广智慧农业应用 3、提升乡村治理智慧化水平 4、丰富智慧乡村生活内容 三、数字乡村打造农村生活新品质的成果展现 1、农业生产效率与质量双提升 2、农民收入与消…

OSCP靶场--Peppo

OSCP靶场–Peppo 考点(ident枚举服务用户名ssh登陆rbash绕过 docker提权) 1.nmap扫描 ## ┌──(root㉿kali)-[~/Desktop] └─# nmap 192.168.158.60 -sV -sC -Pn --min-rate 2500 -p- Starting Nmap 7.92 ( https://nmap.org ) at 2024-04-10 09:32 EDT Nmap scan report…

SQLite数据库在Linux系统上的使用

SQLite是一个轻量级的数据库解决方案&#xff0c;它是一个嵌入式的数据库管理系统。SQLite的特点是无需独立的服务器进程&#xff0c;可以直接嵌入到使用它的应用程序中。由于其配置简单、支持跨平台、服务器零管理&#xff0c;以及不需要复杂的设置和操作&#xff0c;SQLite非…

进程控制(一)

文章目录 1. 进程创建1.1 fork函数初识1.2 fork函数返回值 2. 写时拷贝3. 进程终止3.1 进程退出场景3.2 进程常见退出方法3.3 exit函数3.4 return退出 4. 进程等待4.1 进程等待必要性4.2 进程等待的方法4.2.1 wait方法4.2.2 waitpid方法4.2.3 获取子进程status 1. 进程创建 1.…

MySQL8.0的下载、安装配置教程、连接数据可视图形化界面和卸载及MySQL基本使用教程

文章目录 MySQL8.0下载安装MySQL卸载常见问题解决方式MySQL基本使用教程&#xff08;使用MySQLworkbench&#xff09; 1、创建数据库2、创建表、删除表3、修改表的名字4、为数据表增加、修改、删除字段5、关于修改数据库名字6、拓展&#xff1a;pycharm操作MySQL 首先&#…

uniapp区分app、h5、小程序

APP端 标签内 <!-- #ifdef APP-PLUS --><view> APP端 </view> <!-- #endif --> JSCSS内 /*#ifdef APP-PLUS*/console.log(APP端) /*#endif*/ H5端 标签内 <!-- #ifdef H5 --><view> H5端 </view> <!-- #endif --> JSC…

uniapp中页面滚动锚点位置及滚动到对应高度显示对应按钮

可以把页面代码和组件代码放自己项目里跑一下 页面代码 <template><view class"Tracing-detail"><view class"title" v-for"i in 30">顶部信息</view><!-- tab按钮 --><Tab v-model"activeIndex" …

计算机网络 Telnet远程访问交换机和Console终端连接交换机

一、实验要求和内容 1、配置交换机进入特权模式密文密码为“abcd两位班内学号”&#xff0c;远程登陆密码为“123456” 2、验证PC0通过远程登陆到交换机上&#xff0c;看是否可以进去特权模式 二、实验步骤 1、将一台还没配置的新交换机&#xff0c;利用console线连接设备的…

Vue实现防篡改水印的效果。删除元素无效!更改元素属性无效!支持图片、元素、视频等等。

1、演示 2、水印的目的 版权保护&#xff1a;水印可以在图片、文档或视频中嵌入作者、品牌或版权所有者的信息&#xff0c;以防止未经授权的复制、传播或使用。当其他人使用带有水印的内容时&#xff0c;可以追溯到原始作者或版权所有者&#xff0c;从而加强版权保护。 身份识…

在linux服务器上安装anaconda

遇到问题&#xff1a; 在linux服务器中查看当前有哪些虚拟环境&#xff0c;conda环境用不了&#xff0c;anaconda没有安装&#xff0c;所以要在linux服务器中安装虚拟环境 解决步骤如下&#xff1a; 1.首先下载anaconda的Linux版本的安装包 方法1&#xff1a;官网下载&#…