正则表达式匹配——力扣困难题解

2024-08-25 07:28

本文主要是介绍正则表达式匹配——力扣困难题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣链接:正则表达式匹配
题目描述
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s 的,而不是部分字符串。
在这里插入图片描述
在这里插入图片描述

解题思路

分析字符串

根据上面的示例,首先我们知道 s s s只包含小写字母; p p p包含小写字母、‘.’ 和 ‘*’。
先考虑比较简单的情况,即 p p p不包含’*'。

简单情况的判别

思路如下:

  1. 判断 s s s p p p的长度是否一致。不一致的话,直接return False;一致的话,接着第二步。
  2. 遍历访问 s s s p p p对应位置上的元素,判断是否相等。相等的话(包括 p [ i ] = ′ . ′ p[i] = \ '.\ ' p[i]= . ),继续比对;不相等,直接return False。
for i in range(n):if s[i]==p[i] or p[i] == '.':continueelse:return False
复杂情况的判别——p含有’*’
  1. s = a a b s=aab s=aab, p = a a b c ∗ p=aabc* p=aabc
    p中有 ∗ * ∗ * 前面是c,所以该位置,c可以出现0次、1次或多次
    该case的返回应该是True,即c出现0次 p = a a b p=aab p=aab -> s = p s=p s=p
  2. s = a a c d b f s=aacdbf s=aacdbf, p = a a c d b ∗ f p=aacdb*f p=aacdbf
    p中有 ∗ * ∗ * 前面是b,所以该位置,b可以出现0次、1次或多次
    该case的返回应该是True,即b出现1次 p = a a c d b f p=aacdbf p=aacdbf -> s = p s=p s=p
  3. s = a a c d b b f s=aacdbbf s=aacdbbf, p = a a c d b ∗ f p=aacdb*f p=aacdbf
    p中有 ∗ * ∗ * 前面是b,所以该位置,b可以出现0次、1次或多次
    该case的返回应该是True,即b出现多次 p = a a c d b b f p=aacdbbf p=aacdbbf -> s = p s=p s=p

算法——动态规划

当p含有多个 ∗ * 时,我们无法判别每次 ∗ * 出现时,它前面的那个字符需要出现几次,这种属于动态规划的范围,即都是可商量的。

动态规划——边界情况处理

  1. 定义:
    f [ i ] [ j ] f[i][j] f[i][j]:s[0: i-1]和p[0: j-1]的匹配情况。
    i,j代表的是长度(因为动态规划有个初始值,为了定义初始值一般会有这种错位的情况,即不能认为i,j是下标),所以对应下标就是i-1,j-1。
  2. 初始化数组:
    f=[[False]*(n+1) for _ in range(m+1)]
    初始化边界情况:
    i=0,j=0,f[0][0] = True;
    i=0,j>0,存在f[0][j]= True的情况,需要处理
    i>0,j=0,不存在f[i][0]= True的情况,无需处理
		m=len(s)n=len(p)f=[[False]*(n+1) for _ in range(m+1)]# 初始化f[0][0]f[0][0] = True# 初始化, s:没有字符,p有字符的匹配情况for j in range(1,n+1):if p[j-1] == '*': # 只能匹配0次,查看是否有True的可能#【0次】匹配才能满足【p的变化结果】没有字符f[0][j] = f[0][j-2] # f[0][-1]=f[0][n],不用担心越界

s = a a b s=aab s=aab, p = a a b c ∗ p=aabc* p=aabc,

f[0][0]=True
# 因为 f=[[False]*(n+1) for _ in range(m+1)]
f[0][1]=False 
f[0][2]=False
f[0][3]=False
f[0][4]=False
# 可能True的,会进行动态规划转移
f[0][5]=f[0][3]=False

如果还没看明白,为什么遇到*号,有状态转移,请看下一个例子
s = a a b s=aab s=aab, p = a ∗ a ∗ b ∗ c ∗ p=a*a*b*c* p=aabc,

f[0][0]=True
# 不满足if条件的默认是False,因为 f=[[False]*(n+1) for _ in range(m+1)]
# 可能True的,会进行动态规划转移
f[0][1]=False 
f[0][2]=f[0][0]=True
f[0][3]=False
f[0][4]=f[0][2]=True
f[0][5]=False
f[0][6]=f[0][4]=True
f[0][7]=True
f[0][8]=f[0][6]=True

动态规划——状态转移

p[j-1]不是 ∗ * 时,正常匹配。

if p[j-1]=='.' or s[i-1]==p[j-1]: # 该位置匹配上了,f[i][j]的情况由f[i-1][j-1]决定f[i][j] = f[i-1][j-1] 

p[j-1]是 ∗ * :
如果 ∗ * 号前的字符和s[i-1]匹配上了,可能0次、1次或多次;
如果 ∗ * 号前的字符p[j-2]和s[i-1]没匹配上,只能0次,即舍弃p[j-2]、p[j-1]; (不用担心p[0]=‘*’,因为题目保证了*号前面有有效字符)

if s[i-1] != p[j-2] and p[j-2]!='.': # s[i-1],p[j-2]没匹配上,只能0次f[i][j]=f[i][j-2]
else: # 匹配上了,尝试0次、1次或多次,三者有一个满足True, f[i][j]就是Truef[i][j] = f[i][j-2] | f[i-1][j]

0次: f[i][j] 转移到 f[i][j-2]
1次或多次: f[i][j] 转移到 f[i-1][j],即删掉s[i-1], f[i][j] 的匹配情况由s[0:i-2]和p[0:j-1]的匹配情况(0次、1次或多次)决定。
比如s=‘aaaa’和p=’a*‘,
f[4][2]=f[3][2] # 由4次,转换为3次, 判断s=‘aaa’和p=’a*’
f[3][2]=f[2][2] # 由3次,转换为2次, 判断s=‘aa’和p=’a*’
f[2][2]=f[1][2] # 由2次,转换为1次, 判断s=‘a’和p=’a*’
f[1][2]=f[0][2] # 由1次,转换为0次, 判断s=‘‘和p=’a*’
f[0][2]=f[0][0] # 0次,0次 , 判断s=‘‘和p=’’

解题代码

class Solution:def isMatch(self, s: str, p: str) -> bool:m=len(s)n=len(p)f=[[False]*(n+1) for _ in range(m+1)]# 初始化[0][0]f[0][0] = True# 初始化 '*' f[0][j],匹配0个for j in range(1,n+1):if p[j-1] == '*':f[0][j] = f[0][j-2] # f[0][-1]=f[0][n],不用担心越界for i in range(1,m+1):for j in range(1,n+1):if p[j-1]=='.' or s[i-1]==p[j-1]: # 小写字母匹配上 或 通用的f[i][j] = f[i-1][j-1]elif p[j-1] == '*': # 可0次,1次,多次if s[i-1] != p[j-2] and p[j-2]!='.': # s[i-1],p[j-2]没匹配上,只能0次f[i][j]=f[i][j-2]else: # 匹配上了,尝试0次、1次或多次,三者有一个满足True, f[i][j]就是Truef[i][j] = f[i][j-2] | f[i-1][j]return f[m][n]

复杂度

时间: O ( m n ) O(mn) O(mn),其中 m 和 n 分别是字符串 s 和 p 的长度。我们需要计算出所有的状态,并且每个状态在进行转移时的时间复杂度为 O(1)。
空间: O ( m n ) O(mn) O(mn),即为存储所有状态使用的空间。

这篇关于正则表达式匹配——力扣困难题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104921

相关文章

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

二分最大匹配总结

HDU 2444  黑白染色 ,二分图判定 const int maxn = 208 ;vector<int> g[maxn] ;int n ;bool vis[maxn] ;int match[maxn] ;;int color[maxn] ;int setcolor(int u , int c){color[u] = c ;for(vector<int>::iter

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

OmniGlue论文详解(特征匹配)

OmniGlue论文详解(特征匹配) 摘要1. 引言2. 相关工作2.1. 广义局部特征匹配2.2. 稀疏可学习匹配2.3. 半稠密可学习匹配2.4. 与其他图像表示匹配 3. OmniGlue3.1. 模型概述3.2. OmniGlue 细节3.2.1. 特征提取3.2.2. 利用DINOv2构建图形。3.2.3. 信息传播与新的指导3.2.4. 匹配层和损失函数3.2.5. 与Super

二分图的最大匹配——《啊哈!算法》

二分图 如果一个图的所有顶点可以被分为X和Y两个集合,并且所有边的两个顶点恰好一个属于X,另外一个属于Y,即每个集合内的顶点没有边相连,那么此图就是二分图。 二分图在任务调度、工作安排等方面有较多的应用。 判断二分图:首先将任意一个顶点着红色,然后将其相邻的顶点着蓝色,如果按照这样的着色方法可以将全部顶点着色的话,并且相邻的顶点着色不同,那么该图就是二分图。 java

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹