门户网站设计特点,高端 网站,html网站设计范例,太原模板建站定制网站10. 正则表达式匹配 - 力扣#xff08;LeetCode#xff09;
此题的要求一个字符串 s 和一个字符规律 p之间支持 . 和 * 的正则表达式匹配
. 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配#xff0c;是要涵盖 整个 字符串 s 的#xff0c;而不是部分字符串…10. 正则表达式匹配 - 力扣LeetCode
此题的要求一个字符串 s 和一个字符规律 p之间支持 . 和 * 的正则表达式匹配
. 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配是要涵盖 整个 字符串 s 的而不是部分字符串。
保证每次出现字符 * 时前面都匹配到有效的字符 也就是说p中所有的 * 字符前的那个字符只会是 . 或者字母 示例 1 输入s a, p .* 输出true 示例 2 输入s aab, p c*a*b 输出true 示例 3 输入s a, p a* 输出true 示例 4 输入s a, p .*a 输出true
根据经验和题目要求两个字符串的关系可以考虑二维dp表
能够解决的leetcode中的1143. 最长公共子序列、72. 编辑距离中dp的建立相似
dp[i][j]表示p[0.j]区间内的子串是否能够匹配s[0,i]区间内的子串
状态转移方程根据 p 切出来的子串中的最后一个字符来分情况讨论这种按两个子串的最后一个字符的取值来分情况讨论的方式也是推导状态转移方程的普遍步骤
记记dp[i][j] x; dp[i - 1][j] y; dp[i][j - 2] z dp[i - 1][j - 1] w
则当p[j - 1] 为字母或者 点号时
只用通过 w 和 (s[i - 1] p[j - 1] || p[j - 1] .)这个表达式是否为真就能更新dp[i][j]
当p[j - 1] 为星号时
只用通过y 和 z 和(s[i - 1] p[j - 2] || p[j - 2] .) 这个表达式是否为真就能更新dp[i][j] 图一
读者可能会问了道理我都懂为什么使用了dp[i][j - 2] 来更新dp[i][j]而dp[i][j - 1]却没有使用 让我们来看看图一中 出现p[j - 1] * p[j - 2] . 的情况 此时可以选择产生空串或者将产生一个点号、两个点号等等 那么dp[i][j] dp[i][j - 2] || dp[i - 1][j - 2] || ... dp[i - m][j - 2] || ... (1) 令i u - 1 则有dp[u - 1][j] dp[u - 1][j - 2] || dp[u - 2][j - 2] || ... dp[u - m - 1][j - 2] || ... (2) 观察可知可将2代入1中得到 dp[i][j] dp[i][j - 2] || dp[i - 1][j] 让我们再来看看图一中 出现p[j - 1] * p[j - 2] ! . 的情况 此时可以选择产生空串或者将产生一个p[j - 1]、两个p[j - 1]等等 那么 dp[i][j] dp[i][j - 2] || ((s[i -1] p[j - 2]) (dp[i - 1][j - 2])) || ... ((s[i - m] p[j - 2]) dp[i - m][j - 2] ) || ... (3) 令i v - 1 则有dp[v - 1][j] dp[v - 1][j - 2] || ( (s[v - 2] p[j - 2]) (dp[v - 2][j - 2]) ) || ... ( (s[v - m - 1] p[j - 2]) (dp[v - m - 1][j - 2]) ) || ... (4) 观察可知可将4代入3中然后经过一些列的推导(具体步骤略)可以得到 dp[i][j] dp[i][j - 2] || ( (s[i -1] p[j - 2]) dp[i - 1][j]) 知道这道题为什么用到了dp[i][j - 2]了吧但是还有一个很重要的问题就是在编写这道题的程序的时候可以给这个dp表多加一行多加一列所以
上面在访问原数组是 s[i - 1] 代表的就是第 i 个元素
那么多加的这一行/列是否可以赋予这个题目场景下的具体意义呢
多加的一行可以赋予dp[0][j] 一个意义其意义就是s作为一个空串匹配p[0, j]
如果在这种定义下dp[0][j]要想为truej 和 p[j] 必须满足以下条件才能保证匹配 dp[0, j] 是形如 {{非星号}{星号} {非星号}{星号} {非星号}{星号} {非星号}{星号}} 而dp[i][0] 此时只有在dp[0][0]处会为true
class Solution {
public:bool isMatch(string s, string p) {int len1 s.size();int len2 p.size();vectorvectorbool dp(len1 1, vectorbool(len2 1, false));dp[0][0] true;for(int j 2; j len2; j 2){if(p[j - 1] *){dp[0][j] true;}else{break;}}for(int i 1; i len1; i){for(int j 1; j len2; j){if(p[j - 1] ! *){dp[i][j] ((p[j - 1] s[i - 1] || p[j - 1] .) dp[i - 1][j - 1] true);}else{dp[i][j] ((dp[i][j - 2] true) || ((p[j - 2] s[i - 1] || p[j - 2] .) (dp[i - 1][j] true)));}}}return dp[len1][len2];}
};
