动态规划:LeetCode第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 的小写字母,以及字符 . 和 *
  • 保证每次出现字符 * 时,前面都匹配到有效的字符

思考方向:

1、字符串是否匹配取决于字符串每一位的匹配结果,如果前一位字符都不匹配,则后续将不会再匹配了,所以适合动态规划的结题思路,也即:后面的结果可以由前面的结果推导出来

2、因为字符串匹配是两个字符串,所以采用二维的动态规划

3、*匹配零个或多个前面的那一个元素,这个是结题的关键,尤其是匹配零个,这个经常让我们忽略,比如下例:

输入:s = "a", p = "ab*"

输出:True 

解释:"b" 后面有*,表示b出现了0次。

动态规划的状态转移方程:

我们用 f[i][j]表示 s的前 i个字符与 p中的前 j 个字符是否能够匹配。

在进行状态转移时,我们考虑 p 的第 j 个字符的匹配情况:

1、如果 p 的第 j 个字符是一个小写字母( '.' 匹配任意一个字母,可以看成一个特殊的字母),那么我们必须在 s 中匹配一个相同的小写字母,若相等,只需判断 i,j 之前的字符串是否匹配即可,也就转化为子问题 f[i-1][j-1],若不等,则当前的 i,j 肯定不能匹配,则f[i][j]= false.即可写出公式:

2、如果 p 的第 j 个字符是 *,那么就表示我们可以对 p 的第 j−1 个字符匹配0次或多次,则不妨把类似 'a*', 'b*' 等的当成整体看待:

2.1、如果p[j-1]与s[i]不匹配,那么f[i][j]的匹配情况需要看 f[i][j-2],也就是a*匹配0次(等于没出现a*)的情况,那么也就转化为子问题 f[i][j-2]

2.2、如果p[j-1]与s[i]匹配

2.2.1、最先想到的是一种情况:因为s[i]已经与p[j-1]匹配了,所以我们要看s[i]与p[j−2]的匹配,也就是转化为子问题:f[i][j-2]

2.2.2、其次还有一种情况:2.2.1考虑的是p[j]是p[j-1]重复的情况,本场景需要考虑的是s[i]与s[i-1]相同的情况,那就看s[i−1]与p[j] 的匹配,也就是转化为子问题:f[i-1][j]

2.2.3、综上,那么即可写出公式:

3、最终的状态转换方程如下:

4、状态初始化:

4.1、动态规划的边界条件为 f[0][0]=true,f[0][n](n>0)=false,也就是空字符串s与空字符串p相等,而空字符串s与任何的非空字符串p都不相等。

Python代码:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        sL = len(s)
        pL = len(p)
        f = [[False for j in range(pL + 1)] for i in range(sL + 1)]
        f[0][0] = True
        for i in range(0, sL + 1):
            for j in range(1, pL + 1):
                if p[j - 1] != '*':
                    if match(s,i,p,j):
                        f[i][j] = f[i -1][j - 1]
                else:
                    if match(s,i, p ,j -1):
                        f[i][j] = f[i - 1][j] or f[i][j - 2]
                    else:
                        f[i][j] = f[i][j - 2]
        return f[sL][pL]
        
def match(s, i, p, j):
    if s[i - 1] == p[j - 1]:
        return True
    if p[j - 1] == '.':
        return True
    return False



        

总结:

1、动态规划是逆向思考问题,从后往前进行归纳,也就是思考f(n+1)是如何由f(n)得到的问题

2、动态规划方程的初始化也需要思考清楚,相关的边界条件要想好

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

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

相关文章

C语言文件操作,linux文件操作,文件描述符,linux下一切皆文件,缓冲区,重定向

目录 C语言文件操作 如何打开文件以及打开文件方式 读写文件 关闭文件 Linux系统下的文件操作 open 宏标志位 write&#xff0c;read&#xff0c;close&#xff0c;lseek接口 什么是当前路径&#xff1f; linux下一切皆文件 文件描述符 文件描述符排序 C语言文件操…

【Linux从青铜到王者】进程信号

——————————————————————————————————————————— 信号入门 在了解信号之前有许多要理解的相关概念 我们可以先通过一个生活例子来初步认识一下信号 1.生活角度的信号 你在网上买了很多件商品&#xff0c;再等待不同商品快递的到来…

达梦、金仓、南大、瀚高、优炫:从社区建设看企业技术自信心

正文约950字&#xff0c;预计阅读时间2分钟 国产技术厂商在面对自身产品问题时&#xff0c;往往保持回避态度&#xff0c;不愿公之于众&#xff0c;主要原因有2方面&#xff1a; 1&#xff0c;产品技术层面问题较多&#xff0c;如某些根本性缺陷难以攻克&#xff0c;或问题发…

Python爬虫实战(基础篇)—13获取《人民网》【最新】【国内】【国际】写入Word(附完整代码)

文章目录 专栏导读背景测试代码分析请求网址请求参数代码测试数据分析利用lxml+xpath进一步分析将获取链接再获取文章内容测试代码写入word完整代码总结专栏导读 🔥🔥本文已收录于《Python基础篇爬虫》 🉑🉑本专栏专门针对于有爬虫基础准备的一套基础教学,轻松掌握Py…

vue 安装各种问题

新下载了个项目模板&#xff0c;安装包就遇到了各种各样问题 电脑&#xff1a;mac 使用npm i 等命令一直安装项目&#xff0c;然后一直报错 2534 info run canvas2.11.2 install node_modules/canvas node-pre-gyp install --fallback-to-build --update-binary 2535 info r…

Tomcat+Nginx的动静分离

1.反向代理多机 实验&#xff1a;Nginx要开启upstream(负载均衡)、location(url链接)、proxy_pass(反向代理) 配置&#xff1a;7-3做代理服务器&#xff1b;7-1 和 7-2做Tomcat服务器 关闭防火墙和selinux 1.准备配置 7-3安装nginx&#xff1b;7-1 和 7-2安装Tomcat&#xff…

Re61:读论文 PRP Get an A in Math: Progressive Rectification Prompting

诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文名称&#xff1a;Get an A in Math: Progressive Rectification Prompting ArXiv网址&#xff1a;https://arxiv.org/abs/2312.06867 官方实现网站&#xff1a;PRP 官方代码&#xff1a;https://github.…

iOS 17.0 UIGraphicsBeginImageContextWithOptions 崩溃处理

在升级到iOS17后你会发现&#xff0c;之前版本运行的很好&#xff0c;这个版本突然会出现一个运行闪退。报错日志为*** Assertion failure in void _UIGraphicsBeginImageContextWithOptions(CGSize, BOOL, CGFloat, BOOL)(), UIGraphics.m:410 跟踪到具体的报错位置如下所示&a…

闰年导致的哪些 Bug

每次闰年对程序员们都是一个挑战&#xff0c;平时运行好好的系统&#xff0c;在 02-29 这一天&#xff0c;好像就会有各种毛病。 虽然&#xff0c;提前一天&#xff0c;领导们都会提前给下面打招呼。但是&#xff0c;不可避免的&#xff0c;今天公司因为闰年还是有一些小故障。…

Tomcat(二) 动静分离

一、(TomcatNginx)动静分离 1、单机反向代理 利用 nginx 反向代理实现全部转发至指定同一个虚拟主机 客户端curl www.a.com 访问nginx服务&#xff0c;nginx服务通过配置反向代理proxy_pass www.a.com:8080&#xff0c;最终客户端看到的是www.a.com 实验中&#xff1a;7-3 做客…

码农世界:从入门到高手的成长攻略

&#x1f468;‍&#x1f4bb;&#x1f469;‍&#x1f4bb; 各位编程爱好者&#xff0c;欢迎来到现实而又充满挑战的码农世界。在这里&#xff0c;我们将一起探索一条如何从入门走向精通&#xff0c;最终在IT行业中找到自己位置的道路。准备好笔记本和热情&#xff0c;让我们携…

速通C语言第十三站 预处理

系列文章目录 速通C语言系列 速通C语言第一站 一篇博客带你初识C语言 http://t.csdn.cn/N57xl 速通C语言第二站 一篇博客带你搞定分支循环 http://t.csdn.cn/Uwn7W 速通C语言第三站 一篇博客带你搞定函数 http://t.csdn.cn/bfrUM 速通C语言第四站 一篇博客带…

STM32 NAND FLASH知识点

1.NAND FLASH的简介 NAND FLASH 的概念是由东芝公司在 1989 年率先提出&#xff0c;它内部采用非线性宏单元模式&#xff0c;为固态大容量内存的实现提供了廉价有效的解决方案。 NAND FLASH 存储器具有容量较大&#xff0c;改写速度快等优点&#xff0c;适用于大量数据的存储&…

VR 全景模式OpenGL原理

VR 全景模式OpenGL原理 VR 全景模式原理 VR 全景模式原理将画面渲染到球面上&#xff0c;相当于从球心去观察内部球面&#xff0c;观察到的画面 360 度无死角&#xff0c;与普通播平面渲染的本质区别在渲染图像部分&#xff0c;画面渲染到一个矩形平面上&#xff0c;而全景需…

字节跳动发布SDXL-Lightning模型,支持WebUI与ComfyUI双平台,只需一步生成1024高清大图!

字节跳动发布SDXL-Lightning模型,WebUI与ComfyUI平台,只需一步生成1024高清大图,需要的步数比 LCM 更低了! 什么是SDXL-Lightning: SDXL-Lightning 是一种快速的文本到图像生成模型。SDXL-Lightning模型的核心优势在于其创新的蒸馏策略,它可以通过几个步骤生成高质量的 1…

红黑树的简单介绍

红黑树 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&#x…

服务器出现故障如何恢复数据?

服务器数据恢复案例之服务器raid6中3块硬盘离线导致阵列崩溃的数据恢复案例 服务器故障&#xff1a; 服务器中有一组由6块盘组建的 RAID6&#xff0c;这台网站服务器上运行MYSQL数据库和存放其它类型的文件。该组raid中有两块磁盘离线&#xff0c;管理员没有及时更换磁盘&#…

#QT(智能家居界面-界面切换)

1.IDE&#xff1a;QTCreator 2.实验 3.记录 &#xff08;1&#xff09;创建一个新界面&#xff08;UI界面&#xff09; &#xff08;2&#xff09;可以看到新加入一个ui文件&#xff0c;双击打开&#xff0c;设置窗口大小与登录界面一致 &#xff08;3&#xff09;加入几个PUS…

Linux 运维:CentOS/RHEL防火墙和selinux设置

Linux 运维&#xff1a;CentOS/RHEL防火墙和selinux设置 一、防火墙常用管理命令1.1 CentOS/RHEL 7系统1.2 CentOS/RHEL 6系统 二、临时/永久关闭SELinux2.1 临时更改SELinux的执行模式2.2 永久更改SELinux的执行模式 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;…

【CSP试题回顾】201312-3-最大的矩形

CSP-201312-3-最大的矩形 解题思路 1. 遍历所有可能的矩形高度&#xff1a; 通过遍历所有矩形高度来找到最大的矩形&#xff0c;即对每个可能的高度 it&#xff08;从直方图中的最小高度到最大高度 heightMax&#xff09;&#xff0c;代码将尝试找到在这个高度或以上的最长连…