淘宝客如何做淘宝客网站,《两学一做 榜样》网站,wordpress免签,网站开发总体流程图前言#xff1a;不知不觉又断更一天了#xff0c;其实昨天就把这道题写得差不多了#xff0c;只是刚好在力扣里面看见了一种新的解法#xff0c;本来想写出来的#xff0c;但是我把它推到今天了#xff0c;因为太晚了#xff0c;但是今天又睡懒觉了#xff0c;所以我直…前言不知不觉又断更一天了其实昨天就把这道题写得差不多了只是刚好在力扣里面看见了一种新的解法本来想写出来的但是我把它推到今天了因为太晚了但是今天又睡懒觉了所以我直接写出思路就不写代码了今天在写了这道题的题解之后我觉得我之前写的力扣第十题的题解相比于这道题还是太过于稚嫩了没有抓到主体上面不够通俗易懂都是它的缺点解题思路 1.获取信息 给定一个字符串和一个字符模式 字符模式中包含小写字母以及 * 可以匹配任何单个字符 * 可以匹配任意字符序列包括空字符序列 要求判断字符模式是否能完全匹配字符串 2.分析题目 在看到这道题的时候我想到了之前写过的力扣第十题正则表达式 它也是给定一个字符串和字符模式只不过字符模式中的特殊符号的功能比这道题中的要复杂一些所以这道题可以说是一道简化后的第十题 那么它的方法就不言而喻了与第十题一样是动态规划法但我转念一想要是方法都不怎么改变没有多少新意那怎么能考验自己呢 所以我又尝试用它的核心思想写了一下递归法但是很遗憾在1638个示例的时候超时了不过我还是会讲解一下也许可以帮助你理解 最后我会讲解一下力扣看到的那个新方法也很不错的 3.示例查验 略 4.尝试编写代码 1动态规划法 思路动态规划用小问题来逐步推导出大问题 我们知道在面对通配符肯定是需要考虑多种情况的就以遇到 * 为例 遇到 * 它就会存在两种情况它表示空字符或者表示非空字符 表示空字符那就无事发生 表示非空字符那它可能表示一个字符两个字符或者更多的字符 这些都是需要考虑的情况 实际上动态规划并不能解决我上面说的需要考虑多种情况的难题 动态规划解决的只是一个既定事实的未来发展而已就比如说它的下一步的发展是取决于上一步的确定所以我们动态规划实行的方式如下 先说一下前提我们肯定是要扫描字符来进行匹配的那么以谁为主体开始扫描呢 那肯定是字符模式了因为字符模式中不止存在小写字母 好了说回动态规划 以扫描字符模式为主体会遇到三种情况 1.小写字母比较字符串中对应位置相同则继续不同直接结束 2.可以匹配任意字符直接继续 3. * 需要考虑表示空字符和非空字符的情况 如你所见这些判断都是默认前面的字符完全相匹配的情况下才可以这么判断 并且在遇到 * 动态规划就显得有些手足无措了所以单纯的动态规划不能解决遇到 * 的情况 所以我们如果是个机器要处理这样的问题我们只会遍历完所有的情况让所有的情况都用动态规划走一遍那么只要有一条走得通那么就说明可以匹配 其实核心不怎么在动态规划而是这个遍历完所有的情况的步骤 我们在遇到 * 时就依次遍历* 表示零个字符一个字符两个字符等多个字符的情况只要有一条走得通那么就表示匹配成功 以下是完整代码
class Solution {
public:bool isMatch(string s, string p) {//代码跟力扣第十题大致没有多少区别就不进行注释了int ms.size();int np.size();vectorvectorbooldp(m1,vectorbool(n1,false));dp[m][0]false;dp[0][0]true;for(int j1;jn;j){if(p[j-1]*)dp[0][j]true;else break;}for(int i1;im;i){for(int j1;jn;j){if(p[j-1]*){dp[i][j]dp[i][j-1]||dp[i-1][j];}else if(p[j-1]?){dp[i][j]dp[i-1][j-1];}else{dp[i][j](s[i-1]p[j-1])dp[i-1][j-1];}}}return dp[m][n];}
}; 2递归法 思路上面我们说了遇到星号要依次遍历每种情况我就想到用递归这种方便推行多种情况的方法来对每种情况进行遍历 但是很遗憾如我上面所说在第1638个示例的时候超时了 以下是完整代码
class Solution {
public:bool isMatch(string s, string p) {return GetRes(s,p,0,0,s.size(),p.size());}
private:bool GetRes(strings,stringp,int i,int j,int m,int n){if(jn)return im;if(im){while(jnp[j]*)j;return jn;}if(p[j]*){return GetRes(s,p,i,j1,m,n)||GetRes(s,p,i1,j,m,n);}else if(p[j]?){return GetRes(s,p,i1,j1,m,n);}else{if(s[i]p[j]){return GetRes(s,p,i1,j1,m,n);}else return false;}}
}; 3贪心算法 这是我在力扣上面看到的题解比较惊奇我一开始没有想出来故而记录下来 思路在字符模式中比较麻烦的就是碰到星号其他的符号不值一提 如果没有星号这道题会变得特别简单所以有没有办法去无视星号呢 当然有星号出现零次的情况不用考虑特别简单就直接说星号出现非零次的情况 那么字符模式的样式差不多就是 xxx * xxx * xxx * xxx 等样式 因为星号可以表示任意字符序列所以我们只用判断那些 xxx 的是否存在字符串之中并且它们的相对位置是否一致就可以表明是相匹配的以上就是本次题解了我这个暑假要去学车科目一的题目还没有开始练不知道自己暑假为什么会这么懒惰天天不是玩云顶之弈去找虐就是打排位去找气受不知道我的脑袋里面在想啥唉算了算了我已经把游戏给删掉了顶多每天上线打一下日活不能再堕落下去了提醒纸上得来终觉浅绝知此事要躬行
