本文共 3355 字,大约阅读时间需要 11 分钟。
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
说明:
s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
输入:
s = “aa” p = “a” 输出: false 解释: “a” 无法匹配 “aa” 整个字符串。
输入:
s = “aa” p = “a*” 输出: true 解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。
输入:
s = “aab” p = “cab” 输出: true 解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/regular-expression-matching 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。这次好久没写了,主要是最近在复习高数呢!
这次题呢用到了动态规划,什么是,我的理解就是思路到位,计算机给你全部安排好.
我们来好好看看这个题目是怎么样规划的!先对题目要有大致理解,不要随便的就理解就开始做题了.
如果你了解正则表达式,应该对.和*的作用明白(不知道也没有关系,但请你好好读第二个引用部分)动态规划最难得部分来了
写出转移方程 怎么考虑出状态转移方程? dp[i][j]代表此时前面都匹配成功,不知道接下来的情况. s[i]代表目标字符串 p[j]需要匹配的字符串的表达式 匹配情况分为三种:前面两种情况很简单,第三种就需要细细想想了.
由于*可以0或者多个匹配,所以分两种情况去考虑举个例子:s字符串为"aab" p字符串为"aac*b",你可以看出,当你将 * 作为0个匹配c,那么p字符串就可以当成"aab"与s字符串匹配成功,因为’c’与’b’是不相等的,所以字符串p还往前找一个字符的匹配情况,因为是0匹配,所以,你可以当成不存在,所以此时匹配情况和前两个字符匹配情况是一样的.
我们再举一个例子:用s = “aaab”, p = “ac * a * b”, 第一个 * 是0匹配,第二个 * 是重复一次匹配,那么p可以当成"aab"与s进行匹配成功了.解释与上一个是一样的,‘a’!=‘c’,所以你要字符串p往前面找一个字符的匹配情况,因为这个* 是0匹配,所以,'c’你可以当做不存在.此时匹配情况和前两个字符匹配情况是一样的.
第一种情况在两个例子下应该懂了吧,我们看看多次匹配的情况!
总结一下:
基本就这样吧!!!我是这样理解的,如果有什么疑问,可以评论提出.
class Solution { public: bool isMatch(string s, string p) { bool dp[s.length()+1][p.length()+1]={ false};//c++这里要默认初始化不然编译环境不同可能会出问题比如:VS默认true{xxx}。 dp[0][0]=true;//dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配 //对p情况的a*b*c*匹配空的s 进行预处理,并且初始化 for(int i=0;i
我懒得的写注释,所以抄了一下别人写好的代码,其实考虑的方向是一样的.
可以多看看.
class Solution { public: vector> res; string s,p; bool isMatch(string _s, string _p) { s=_s; p=_p; res=vector(s.size()+1,vector(p.size()+1,-1)); return Best(0,0); } bool Best(int i,int j){ if(res[i][j]!=-1) return res[i][j]; if(j==p.size()) return res[i][j]=i==s.size(); bool fm=i
多学习是我们的代言.
我感觉自己讲的应该清晰吧!!如果有任何问题可以评论找我.最近买了一本游戏编程入门,接下几个月有的玩了.哈哈哈哈!!
你们好!我是大一小菜鸡,又菜瘾还大