合肥网站优化方案,网站备案登陆用户名是什么,专业网站制作公司采用哪些技术制作网站?,湖南众诚建设 官方网站10. 正则表达式匹配
链接: 10. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p#xff0c;请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配#xff0c;是要涵盖 整个 字符串 s的#xf…10. 正则表达式匹配
链接: 10. 正则表达式匹配 给你一个字符串 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.状态表示*
dp[i][j] 表⽰字符串 p 的 [0, j] 区间和字符串 s 的 [0, i] 区间是否可以匹配
2.状态转移方程 ⽼规矩根据最后⼀个位置的元素结合题⽬要求分情况讨论
i. 当 s[i] p[j] 或 p[j] . ’ 的时候此时两个字符串匹配上了当前的⼀个字符只能从 dp[i - 1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果 dp[i][j] dp[i][j - 1] ii. 当 p[j] ‘*’ 的时候此时匹配策略有两种选择 • ⼀种选择是 * 匹配空字符串此时相当于它匹配了⼀个寂寞直接继承状态 dp[i] [j - 1] 此时 dp[i][j] dp[i][j -1] • 另⼀种选择是 * 向前匹配 1 ~ n 个字符直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 k i) 中所有匹配情况中选择性继承可以成功的情况。此时 dp[i][j] dp[k][j - 1] (0 k i) iii. 当 p[j] 不是特殊字符且不与 s[i] 相等时⽆法匹配。 三种情况加起来就是所有可能的匹配结果。
综上所述状态转移⽅程为
▪ 当 s[i] p[j] 或 p[j] ‘?’ 时 dp[i][j] dp[i][j - 1] ▪ 当 p[j] ‘*’ 时有多种情况需要讨论 dp[i][j] dp[k][j - 1] (0 k i)
3. 初始化 由于 dp 数组的值设置为是否匹配为了不与答案值混淆我们需要将整个数组初始化为false 。 由于需要⽤到前⼀⾏和前⼀列的状态我们初始化第⼀⾏、第⼀列即可。 dp[0][0] 表⽰两个空串能否匹配答案是显然的初始化为 true 。
第⼀⾏表⽰ s 是⼀个空串 p 串和空串只有⼀种匹配可能即 p 串全部字符表⽰为任⼀字符*此时也相当于空串匹配上空串。所以我们可以遍历 p 串把所有前导为任⼀字符的 p ⼦串和空串的 dp 值设为 true 。 第⼀列表⽰ p 是⼀个空串不可能匹配上 s 串跟随数组初始化即可
4. 填表顺序 根据「状态转移⽅程」得从上往下填写每⼀⾏每⼀⾏从左往右
5. 返回值 返回 dp[m][n]
代码 bool isMatch(string s, string p) {int ns.size();int mp.size();//表示的是 s串中0~i 位置的子串能否于 p串 0~j 上完全匹配vectorvectorbool dp(n1,vectorbool(m1,false));//初始化dp[0][0]true;for(int i2;im;i2)//初始化有坑{if(p[i-1]*) dp[0][i]1;else break;}//填表for(int i1;in;i){for(int j1;jm;j){if(s[i-1]p[j-1]||p[j-1].){dp[i][j]dp[i-1][j-1];}if(p[j-1]*){if(p[j-2].){dp[i][j]dp[i][j-2]||dp[i-1][j];}else{if(p[j-2]s[i-1])//相等的时候dp[i][j]dp[i][j-2]||dp[i-1][j];//当不相等的时候也需要考虑匹配空串的情况else dp[i][j]dp[i][j-2];}}}}return dp[n][m];}97. 交错字符串
链接: 97. 交错字符串
给定三个字符串 s1、s2、s3请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。
两个字符串 s 和 t 交错 的定义与过程如下其中每个字符串都会被分割成若干 非空 子字符串
s s1 s2 … sn t t1 t2 … tm |n - m| 1 交错 是 s1 t1 s2 t2 s3 t3 … 或者 t1 s1 t2 s2 t3 s3 … 注意a b 意味着字符串 a 和 b 连接。 示例 2
输入s1 “aabcc”, s2 “dbbca”, s3 “aadbbbaccc” 输出false 示例 3
输入s1 “”, s2 “”, s3 “” 输出true
1.状态表示*
dp[i][j] 表⽰字符串 s1 中 [1, i] 区间内的字符串以及 s2 中 [1, j] 区间内的字符串能否拼接成 s3 中 [1, i j] 区间内的字符串。
2.状态转移方程 先分析⼀下题⽬题⽬中交错后的字符串为 s1 t1 s2 t2 s3 t3… 看 似⼀个 s ⼀个 t 。实际上 s1 能够拆分成更⼩的⼀个字符进⽽可以细化成 s1 s2 s3 t1 t2 s4… 。 也就是说并不是前⼀个⽤了 s 的⼦串后⼀个必须要⽤ t 的⼦串。这⼀点理解对我们的状态转移很重要。
继续根据两个区间上「最后⼀个位置的字符」结合题⽬的要求来进⾏「分类讨论」
i. 当 s3[i j] s1[i] 的时候说明交错后的字符串的最后⼀个字符和 s1 的最后⼀个字符匹配了。那么整个字符串能否交错组成变成 s1 中[1, i - 1] 区间上的字符串以及 s2 中 [1, j] 区间上的字符串能够交 错形成 s3 中 [1, i j - 1] 区间上的字符串也就是 dp[i - 1][j] 此时 dp[i][j] dp[i - 1][j]ii. 当 s3[i j] s2[j] 的时候说明交错后的字符串的最后⼀个字符和 s2 的最后 ⼀个字符匹配了。那么整个字符串能否交错组成变成 s1 中 [1, i] 区间上的字符串以及 s2 中 [1, j - 1] 区间上的字符串能够交 错形成 s3 中 [1, i j - 1] 区间上的字符串也就是dp[i][j - 1] iii. 当两者的末尾都不等于 s3 最后⼀个位置的字符时说明不可能是两者的交错字符串。
上述三种情况下只要有⼀个情况下能够交错组成⽬标串就可以返回 true 。因此我们可以定义状态转移为 dp[i][j] (s1[i - 1] s3[i j - 1] dp[i - 1][j])|| (s2[j - 1] s3[i j - 1] dp[i][j - 1])
3. 初始化 于⽤到 i - 1 , j - 1 位置的值因此需要初始化「第⼀个位置」以及「第⼀⾏」和「第⼀列」。 第⼀个位置 dp[0][0] true 因为空串空串能够构成⼀个空串。
第⼀⾏ 第⼀⾏表⽰ s1 是⼀个空串我们只⽤考虑 s2 即可。因此状态转移之和 s2 有关 dp[0][j] s2[j - 1] s3[j - 1] dp[0][j - 1] j 从 1 到 n
第⼀列 第⼀列表⽰ s2 是⼀个空串我们只⽤考虑 s1 即可。因此状态转移之和 s1 有关 dp[i][0] s1[i - 1] s3[i - 1] dp[i - 1][0] i 从 1 到 m
4. 填表顺序 根据「状态转移⽅程」得从上往下填写每⼀⾏每⼀⾏从左往右
5. 返回值 返回 dp[m][n]
代码 bool isInterleave(string s1, string s2, string s3) {int ns1.size();int ms2.size();if(mn!s3.size()) return false;s1 s1;s2 s2;s3 s3;//表示的是s1中前i位置的和s2中前j位置能否和s3中前 ij 位置进行组成vectorvectorbool dp(n1,vectorbool(m1));dp[0][0]true;for(int i1;im;i){if(s2[i]s3[i]) dp[0][i]true;else break;}for(int j1;jn;j){if(s1[j]s3[j]) dp[j][0]true;else break;}for(int i1;in;i){for(int j1;jm;j){if(s1[i]s3[ij]dp[i-1][j]){dp[i][j]true;}if(s2[j]s3[ij]dp[i][j-1]){dp[i][j]true;}}}return dp[n][m];}
