雨燕直播,东莞搜索网络优化,可以转app的网站怎么做,房产达人目录
编辑
一#xff0c;通符串匹配
1.题目
2.题目接口
3#xff0c;解题思路及其代码
二#xff0c;正则表达 1.题目
2.题目接口
3.解题思路及其代码
三#xff0c;交错字符串 1.题目
2#xff0c;题目接口
3.解题思路及其代码 一#xff0c;通符串匹配
1…
目录
编辑
一通符串匹配
1.题目
2.题目接口
3解题思路及其代码
二正则表达 1.题目
2.题目接口
3.解题思路及其代码
三交错字符串 1.题目
2题目接口
3.解题思路及其代码 一通符串匹配
1.题目 给你一个输入字符串 (s) 和一个字符模式 (p) 请你实现一个支持 ? 和 * 匹配规则的通配符匹配 ? 可以匹配任何单个字符。* 可以匹配任意字符序列包括空字符序列。 判定匹配成功的充要条件是字符模式必须能够 完全匹配 输入字符串而不是部分匹配。 示例 1 输入s aa, p a
输出false
解释a 无法匹配 aa 整个字符串。示例 2 输入s aa, p *
输出true
解释* 可以匹配任意字符串。示例 3 输入s cb, p ?a
输出false
解释? 可以匹配 c, 但第二个 a 无法匹配 b。提示 0 s.length, p.length 2000s 仅由小写英文字母组成p 仅由小写英文字母、? 或 * 组成 2.题目接口
class Solution {
public:bool isMatch(string s, string p) {}
};
3解题思路及其代码 在做动态规划问题时一般都是按照以下几步来走的 1.确定状态转移方程 像这种两个字符串的问题一般都是定义二维的dp表按照两个字符串的第i和j下标位置来解决问题的。所以在这里定义dp[i][j]表示p在区间[1,j]中的字符是否存在能够匹配s在[1i]中的字符。 2.状态转移方程 以s的第i个位置p的第j个位置为研究对象来研究问题。此时分三种情况1.s[i] p[j]或者p[j] ?,在这种情况下dp[i][j] dp[i-1][j-1]。 2.p[j] *在这种情况下就要看这个*可以顶替掉多少个s中的字符了 顶替0个dp[i][j] dp[i][j-1] 顶替1个dp[i][j] dp[i-1][j-1] 顶替2个dp[i][j] dp[i-2][j-1] 顶替3个dp[i][j] dp[i-3][j-1]...... 在以上i种情况下我们只要找到一个为真便可以了。所以dp[i][j] dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1].....。但是这样表示的话就需要遍历一遍所以我们必须要优化以上状态表达优化成为dp[i][j] dp[i][j-1]||dp[i-1][j]。通过数学推导得知将dp[i][j-1]后面的表达式转为一个状态表示。 3.s[i]!p[j]并且不是以上情况在这种条件下dp[i][j]直接就是false。 3.初始化 1.在字符串问题里我们一般会在字符串的开头加上一个 。 2.因为*是可以匹配空的所以当s字符串为空串时p为空串或者p全为*时也是可以匹配的。 初始化如下 s s;
p p;dp[0][0] true;
//初始化当我的s是一个空串时我的p都是*
for(int i 1;in1;i) if(dp[0][i-1]p[i] *) dp[0][i] true; 4.填表顺序 根据状态转移方程很容易得出dp表的填写顺序是从左到右从上到下。 5.返回值 根据状态表示可知返回值是dp[m][n](m表示s的长度n表示p的长度) 代码 class Solution {
public:bool isMatch(string s, string p) {int m s.size();int n p.size();vectorvectorbooldp(m1,vectorbool(n1));//dp[i][j]表示s,p分别以i,j结尾能不能完全匹配s s;p p;dp[0][0] true;//初始化当我的s是一个空串时我的p都是*for(int i 1;in1;i) if(dp[0][i-1]p[i] *) dp[0][i] true;//以i,j为结尾研究问题for(int i 1;im1;i){for(int j 1;jn1;j){//分两种情况if(p[j] s[i]||p[j] ?){dp[i][j] dp[i-1][j-1];}else if(p[j] *){//这颗*可以若干个字符那可以配0个或者无数个得到的状态转移方程如下//如果不匹配dp[i][j] dp[i][j-1]//如果匹配1个dp[i][j] dp[i-1][j-1]//如果匹配两个dp[i][j] dp[i-2][j-1]//.......//在上面的情况中我们只要找到一种便可以//dp[i][j] dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||dp[i-3][j-1]......//优化将上面的i个表达式变成n个表达式表示dp[i][j] dp[i][j-1]||dp[i-1][j] dp[i][j] dp[i-1][j]||dp[i][j-1];}}} return dp[m][n];}
}; 二正则表达 1.题目 给你一个字符串 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 201 p.length 20s 只包含从 a-z 的小写字母。p 只包含从 a-z 的小写字母以及字符 . 和 *。保证每次出现字符 * 时前面都匹配到有效的字符 2.题目接口
class Solution {
public:bool isMatch(string s, string p) {}
};
3.解题思路及其代码 但是这道题跟第一道题何其相似啊.和?匹配规则是一样的但是注意两个题目的*的匹配规则是是不一样的。所以在*和初始化处就要稍加改造了改造如下 初始化 for(int i 2;in1;i2) if(dp[0][i-2]p[i] *) dp[0][i] true; 当遇到*时填表情况如下 else if(p[j] *){//按照题意在*前面一定有字符if(p[j-1] .)//无敌匹配{dp[i][j] dp[i][j-2]||dp[i-1][j];}else//不是.{//判断后再匹配if(p[j-1] s[i]){dp[i][j] dp[i][j-2]||dp[i-1][j];}else{dp[i][j] dp[i][j-2];}} 解题代码如下 class Solution {
public:bool isMatch(string s, string p) {int m s.size();int n p.size();//经典加上空格s s;p p;//经典二维dp表vectorvectorbooldp(m1,vectorbool(n1));dp[0][0] true;//初始化:当s为空串时for(int i 2;in1;i2) if(dp[0][i-2]p[i] *) dp[0][i] true;for(int i 1;im1;i){for(int j 1;jn1;j){//分情况讨论if(p[j] .||s[i] p[j]){//i,j位置匹配上了就得看dp[i-1][j-1]dp[i][j] dp[i-1][j-1];}else if(p[j] *){//按照题意在*前面一定有字符if(p[j-1] .)//无敌匹配{dp[i][j] dp[i][j-2]||dp[i-1][j];}else//不是.{//判断后再匹配if(p[j-1] s[i]){dp[i][j] dp[i][j-2]||dp[i-1][j];}else{dp[i][j] dp[i][j-2];}}}}}return dp[m][n];}
}; 三交错字符串 1.题目 给定三个字符串 s1、s2、s3请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下其中每个字符串都会被分割成若干 非空 子字符串 s s1 s2 ... snt t1 t2 ... tm|n - m| 1交错 是 s1 t1 s2 t2 s3 t3 ... 或者 t1 s1 t2 s2 t3 s3 ... 注意a b 意味着字符串 a 和 b 连接。 示例 1 输入s1 aabcc, s2 dbbca, s3 aadbbcbcac
输出true示例 2 输入s1 aabcc, s2 dbbca, s3 aadbbbaccc
输出false示例 3 输入s1 , s2 , s3
输出true提示 0 s1.length, s2.length 1000 s3.length 200s1、s2、和 s3 都由小写英文字母组成 进阶您能否仅使用 O(s2.length) 额外的内存空间来解决它? 2题目接口
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {}
};
3.解题思路及其代码 在看到三个字符串时我就已经犯蒙了。感觉二维的dp表好像已经解决不了问题了但是其实是可以解决问题的。解决步骤如下 1状态表示 仍然是开一个二维dp表dp[][]。仍然以s1的第i个位置和s2的第j个位置为研究对象研究问题。dp[i][j]表示s1的【1i]区间和s2的【1j】区间的字符能不能组成s3的【1ij】区间的字符。 2.状态转移方程 在这里我们也是分两种情况来讨论 1当s1[i] s3[ij]时dp[i][j] dp[i-1][j]。 2 当s2[j] s3[ij]时dp[i][j] dp[i][j-1]。 3, 当以上两种情况都不成立的话dp[i][j] false。 所以dp[i][j] (s1[i]s3[ij]dp[i-][j])(s2[j] s3[ij]dp[i][j-1])。 3初始化 为了让下标对应所以得在每个字符的前面加上 。 //加上空格因为空格有意义s1 s1;s2 s2;s3 s3; 当s1和s2都是空串时能够组成空串 //初始化
dp[0][0] true; 当有一个串为空时另一个串要和s3一一匹配 for(int i 1;im1;i)//代表s2为空串{if(s1[i] s3[i]){dp[i][0] true;}else {break;}}for(int i 1;in1;i)//代表s1为空串{if(s2[i] s3[i]){dp[0][i] true;}else{break;}} 4填表顺序 按照状态转移方程可知填表顺序为从上到下从左到右。 5返回值 返回dp[m][n] 代码如下 class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m s1.size();int n s2.size();if(mn!s3.size()) return false;//二维数组表示以i,j位置为结尾能够组成s3的ijvectorvectorbooldp(m1,vectorbool(n1));//加上空格因为空格有意义s1 s1;s2 s2;s3 s3;//初始化dp[0][0] true;for(int i 1;im1;i)//代表s2为空串{if(s1[i] s3[i]){dp[i][0] true;}else {break;}}for(int i 1;in1;i)//代表s1为空串{if(s2[i] s3[i]){dp[0][i] true;}else{break;}}//经典以i,j位置为研究对象for(int i 1;im1;i){for(int j 1;jn1;j){dp[i][j] (s1[i] s3[i j] dp[i - 1][j])|| (s2[j] s3[i j] dp[i][j - 1]);}}return dp[m][n];}
}; 文章转载自： http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.ldqzz.cn.gov.cn.ldqzz.cn http://www.morning.pkwwq.cn.gov.cn.pkwwq.cn http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.zlhzd.cn.gov.cn.zlhzd.cn http://www.morning.wrlff.cn.gov.cn.wrlff.cn http://www.morning.yrnrr.cn.gov.cn.yrnrr.cn http://www.morning.snrhg.cn.gov.cn.snrhg.cn http://www.morning.wlqll.cn.gov.cn.wlqll.cn http://www.morning.pdynk.cn.gov.cn.pdynk.cn http://www.morning.rbjth.cn.gov.cn.rbjth.cn http://www.morning.zqkms.cn.gov.cn.zqkms.cn http://www.morning.rgnp.cn.gov.cn.rgnp.cn http://www.morning.tbksk.cn.gov.cn.tbksk.cn http://www.morning.drtgt.cn.gov.cn.drtgt.cn http://www.morning.ghgck.cn.gov.cn.ghgck.cn http://www.morning.npcxk.cn.gov.cn.npcxk.cn http://www.morning.tfpmf.cn.gov.cn.tfpmf.cn http://www.morning.krdmn.cn.gov.cn.krdmn.cn http://www.morning.weiwt.com.gov.cn.weiwt.com http://www.morning.dnqliv.cn.gov.cn.dnqliv.cn http://www.morning.sqfrg.cn.gov.cn.sqfrg.cn http://www.morning.yjfmj.cn.gov.cn.yjfmj.cn http://www.morning.skdhm.cn.gov.cn.skdhm.cn http://www.morning.bwdnx.cn.gov.cn.bwdnx.cn http://www.morning.tbjtm.cn.gov.cn.tbjtm.cn http://www.morning.tzrmp.cn.gov.cn.tzrmp.cn http://www.morning.xsbhg.cn.gov.cn.xsbhg.cn http://www.morning.dncgb.cn.gov.cn.dncgb.cn http://www.morning.gccrn.cn.gov.cn.gccrn.cn http://www.morning.fpxms.cn.gov.cn.fpxms.cn http://www.morning.spqbp.cn.gov.cn.spqbp.cn http://www.morning.tzkrh.cn.gov.cn.tzkrh.cn http://www.morning.ptmsk.cn.gov.cn.ptmsk.cn http://www.morning.nlkhr.cn.gov.cn.nlkhr.cn http://www.morning.paoers.com.gov.cn.paoers.com http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.ngcsh.cn.gov.cn.ngcsh.cn http://www.morning.nlgyq.cn.gov.cn.nlgyq.cn http://www.morning.ndngj.cn.gov.cn.ndngj.cn http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.jgcxh.cn.gov.cn.jgcxh.cn http://www.morning.rpstb.cn.gov.cn.rpstb.cn http://www.morning.807yy.cn.gov.cn.807yy.cn http://www.morning.gjqgz.cn.gov.cn.gjqgz.cn http://www.morning.pgmyn.cn.gov.cn.pgmyn.cn http://www.morning.sxwfx.cn.gov.cn.sxwfx.cn http://www.morning.ydhmt.cn.gov.cn.ydhmt.cn http://www.morning.ppgdp.cn.gov.cn.ppgdp.cn http://www.morning.hmnhp.cn.gov.cn.hmnhp.cn http://www.morning.dfkby.cn.gov.cn.dfkby.cn http://www.morning.yxplz.cn.gov.cn.yxplz.cn http://www.morning.kflzy.cn.gov.cn.kflzy.cn http://www.morning.wzwyz.cn.gov.cn.wzwyz.cn http://www.morning.zqybs.cn.gov.cn.zqybs.cn http://www.morning.rmjxp.cn.gov.cn.rmjxp.cn http://www.morning.jhrkm.cn.gov.cn.jhrkm.cn http://www.morning.rqckh.cn.gov.cn.rqckh.cn http://www.morning.tyjnr.cn.gov.cn.tyjnr.cn http://www.morning.kfwqd.cn.gov.cn.kfwqd.cn http://www.morning.mbaiwan.com.gov.cn.mbaiwan.com http://www.morning.nfqyk.cn.gov.cn.nfqyk.cn http://www.morning.dpbgw.cn.gov.cn.dpbgw.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.pbtrx.cn.gov.cn.pbtrx.cn http://www.morning.xptkl.cn.gov.cn.xptkl.cn http://www.morning.gmrxh.cn.gov.cn.gmrxh.cn http://www.morning.znqmh.cn.gov.cn.znqmh.cn http://www.morning.xykst.cn.gov.cn.xykst.cn http://www.morning.bbgn.cn.gov.cn.bbgn.cn http://www.morning.lsxabc.com.gov.cn.lsxabc.com http://www.morning.jlmrx.cn.gov.cn.jlmrx.cn http://www.morning.jkzjs.cn.gov.cn.jkzjs.cn http://www.morning.kmlmf.cn.gov.cn.kmlmf.cn http://www.morning.ylsxk.cn.gov.cn.ylsxk.cn http://www.morning.znqfc.cn.gov.cn.znqfc.cn http://www.morning.yrctp.cn.gov.cn.yrctp.cn http://www.morning.rzcmn.cn.gov.cn.rzcmn.cn http://www.morning.lfbsd.cn.gov.cn.lfbsd.cn http://www.morning.wqpsf.cn.gov.cn.wqpsf.cn
