博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
LeetCode 10. Regular Expression Matching / 44. Wildcard Matching
阅读量:5824 次
发布时间:2019-06-18

本文共 2102 字,大约阅读时间需要 7 分钟。

10. Regular Expression Matching

经典DP题目,比较复杂,需要多复习。

dp[i][j] 表示 s 下标0~i,p 下标0~j 是否能够匹配

                 dp[i-1][j-1]    s[i]==p[j] || p[j]=='.'

dp[i][j] =     dp[i][j-2]       p[j]=='*', 0 occurence      

       dp[i-1][j]      p[j]=='*', s[i]==p[j-1] || p[j-1]=='.'

第一行是 p[j]!='*'的情况;后两行是p[j]=='*'的情况

dp[s.size()-1][p.size()-1] 为所求

 

为了方便,把dp[i][j]定义换为 s的前i个字符,p的前j个字符,设置dp[0][0] = true,可以方便base case的初始化。需要注意下标的对应。

base case 需要初始化所有 dp[i][0] 和 dp[0][j],其中dp[i][0] 都是false不用管,dp[0][j]不一定,利用dp[0][0]=ture初始化,和计算dp时写在一起。

 

写的时候注意下标要合法,dp[i][j] 中的 i, j 都要≥0,字符串的下标也要≥0。

p[j-1]!='*'时 dp[i][j] = dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.') 的条件为 i≥1,j≥1

p[j-1]=='*',大前提是*前面还有一个字符,因此 j-1≥1 -> j≥2

                 dp[i][j] = dp[i][j-2] 要求 i≥0,这里当i=0时,就是在初始化dp[0][j]的base case

                 dp[i][j] = dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.') 要求i≥1

 

class Solution {public:    bool isMatch(string s, string p) {        vector
> dp(s.size()+1, vector
(p.size()+1, false)); dp[0][0] = true; for (int i=0;i<=s.size();++i){ for (int j=1;j<=p.size();++j){ if (j>=2 && p[j-1]=='*'){ dp[i][j] = dp[i][j-2] || i>=1 && dp[i-1][j] && (s[i-1]==p[j-2] || p[j-2]=='.'); }else{ dp[i][j] = i>=1 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='.'); } } } return dp[s.size()][p.size()]; }};

 

 

44. Wildcard Matching

几乎和正则匹配一样,除了这里的 "*" 是不需要前面有一个字符的,写起来实际比正则匹配更容易。

同样把 dp[0][j] 的初始化写在了更新dp的里面。

class Solution {public:    bool isMatch(string s, string p) {        vector
> dp(s.size()+1, vector
(p.size()+1, false)); dp[0][0] = true; for (int i=0;i<=s.size();++i){ for (int j=1;j<=p.size();++j){ if (p[j-1]=='*') dp[i][j] = dp[i][j-1] || i>=1 && dp[i-1][j]; else dp[i][j] = i>=1 && dp[i-1][j-1] && (s[i-1]==p[j-1] || p[j-1]=='?'); } } return dp[s.size()][p.size()]; }};

 

转载于:https://www.cnblogs.com/hankunyan/p/9711046.html

你可能感兴趣的文章
兰州青年志愿者“中西合璧”玩快闪 温暖旅客回家路
查看>>
计划10年建10万廉价屋 新西兰政府:比想象中难
查看>>
甘肃发首版《3D打印职业教育教材》:校企合作育专才
查看>>
内蒙古2019年精准脱贫新“目标”:20个贫困旗县全部摘帽
查看>>
韩国国会议员涉嫌投机炒房 检方称已立案调查
查看>>
李娜入选国际网球名人堂 成亚洲第一人
查看>>
为找好心人抚养孩子 浙江一离婚父亲将幼童丢弃公园
查看>>
晚婚晚育 近20年巴西35岁以上孕妇增加65%
查看>>
读书:为了那个美妙的咔哒声
查看>>
我从过去八个月的AI公司面试中学到了什么?
查看>>
jQuery实践小结
查看>>
深入探究Immutable.js的实现机制(一)
查看>>
jsp改造之sitemesh注意事项
查看>>
iOS底层原理总结 - 探寻block的本质(二)
查看>>
智能硬件的时代,嵌入式是否已经日薄西山
查看>>
单点登录(SSO)看这一篇就够了
查看>>
SpringBoot-Shiro使用
查看>>
分布式理论:CAP是三选二吗?
查看>>
iOS 9.0之后NSString encode方法替换
查看>>
解决 ThinkPHP5 无法接收 客户端 Post 传递的 Json 参数
查看>>