公司怎么做网站推广,搜索引擎原理,大连网站制作公司费用多少,免费做流程图的网站文章目录题目思路转移方程特征再探 i 和 j代码题目
请实现一个函数用来匹配包含 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符#xff0c;而 * 表示它前面的字符可以出现任意次#xff08;含0次#xff09;。在本题中#xff0c;匹配是指字符串的所有字符匹配整…
文章目录题目思路转移方程特征再探 i 和 j代码题目
请实现一个函数用来匹配包含 . 和 * 的正则表达式。模式中的字符 . 表示任意一个字符而 * 表示它前面的字符可以出现任意次含0次。在本题中匹配是指字符串的所有字符匹配整个模式。例如字符串 aaa 与模式 a.a 和 ab*ac*a 匹配但与 aa.a 和 ab*a 均不匹配。
来源力扣LeetCode 思路 再一次膜拜大佬 作者jyd 本文基于大佬的思路做自己的细节解析。 其实动规的难点一直在于“找规律”。恐怕这也是所有算法题的难点哈哈
本题其实就是在考察程序员思考问题的全面性。
转移方程
先建立这道题的转移方程
用 f[i][j] 代表 s 的前 i 个和 p 的前 j 个能否匹配。
当正则表达式中为 正常字符 和 . 时问题是很好解决的
f[i][j]f[i−1][j−1]前 i 个 s 和 前 j 个 p 是否匹配还要看 前 i-1 个 s 和 前 j-1 个 p 是否匹配。
难点就在于是 字符 * 时该怎么处理
分为将字符看成 出现0次也就是不看这两位和 出现多次看这个组合
不看直接砍掉正则串的后面两个 f[i][j] f[i][j-2]看正则串不动主串前移一个f[i][j] f[i-1][j]
上面两点大部分题解已经说的很明白了但其实又很抽象。我们不妨用例子来看一下
第一种比较好理解 —— f[i][j] f[i][j-2]
sabcd pabcde*
将主串的最后一位视为 ia正则串最后一位视为 j*。显而易见两个字符串是完全匹配的。只需要 * 前面的 ej-1 出现0次就可正则串里面的 d 就是 j-2。
第二种理解起来可能有点抽象 —— f[i][j] f[i-1][j]
sabccc pabc*
此时 i为c 、j为*因为 *前面的字符 可以 出现多次也就是出现1次的递归操作。因此此时我们做的操作就是
已经知道了 i 是 j也就是*前的字符 那么再试着看看 i-1 还是不是 j。
也就是原本相互匹配的字符我们不看了都做-1操作i 和 j 彼此是匹配的理应再看 i-1 和 j-1但是我们想要 j 多出现几次因此 j-1 的操作没有执行。这就是下图中jyd大佬所说的 p[j-2]多出现1次。 图中总说 s[i-1] p[j-1] 为什么不是直接用 s[i] p[j] 呢这个问题讲完初始化dp数组首行我们再细说。
特征
弄懂了主要的验证是否匹配的操作接下来我们需要弄懂一些特例
首先明晰一点正则串和主串都是可以为空串的。
空主串和空正则是匹配的。非空串和空正则必不匹配。空主串和非空正则不能直接判定匹配与否。非空串和非空正则那肯定是需要计算的了。
我们可以根据上面的特征来初始化dp二维数组。
行代表s列代表pdp[0][j] 代表s为空dp[i][0]代表p为空。
第四点其实就是我们的转移方程。因此我们来详解一下第三点
当s 时pa*b*c* 和 pab* 前者可以做到和空主串完美匹配后者却不行。因此我们可以得出以下规律 因此可以得到初始化dp首行的代码首列无需做多余更改空正则除了匹配空主串其余皆不匹配
// 初始化dp首行
dp[0][0] 1;
for(size_t i 2; i cols; i 2){dp[0][i] dp[0][i-2] p[i-1] *;
}再探 i 和 j
我读完大佬写的题解的时候其实还是很懵懂的真正豁然开朗是看了大佬的图解。大佬做图解一直有一手的~
下面结合图解来讲一下我们遗留的问题dp[i][j] 和与之相对应的 s[i-1] p[j-1]。
我们借用一下大佬的图来看一下 我们会发现前面提到
第一行也就是下标为0的那行代表 s 为空串第一列也就是下标为0的那列代表 p 为空串
我们是从第二行下标为1的行和第二列下标为1的列开始保存 s 和 p 的非空部分的。
因此举个具体的例子dp[1][1]其逻辑含义是保存的值表示 前1个s 和前1个p 是否匹配。在物理上代表 s[0] 和 p[0] 组成的点。因此我们也就不难理解大佬图解中频繁出现的 dp[i][j] 和 s[i-1] p[j-1] 之间的关系了。 代码
class Solution {
public:bool isMatch(string s, string p) {int rows s.size()1;int cols p.size()1;vectorvectorint dp(rows, vectorint(cols, 0));// 初始化dp首行dp[0][0] 1;for(size_t i 2; i cols; i 2){dp[0][i] dp[0][i-2] p[i-1] *;}// 动规for(size_t i 1; i rows; i){for(size_t j 1; j cols; j){if(p[j-1] ! *){if(dp[i-1][j-1] (s[i-1]p[j-1] || p[j-1] .)){dp[i][j] 1;}}else{if(dp[i][j-2] || (dp[i-1][j] (s[i-1] p[j-2] || p[j-2] .))){dp[i][j] 1;}}}}return dp[rows-1][cols-1];}
};
