lua正则匹配只匹配第一个_leetcode10.正则表达式匹配

leetcode10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p&＃xff0c;请你来实现一个支持 &＃39;.&＃39; 和 &＃39;*&＃39; 的正则表达式匹配。

所谓匹配&＃xff0c;是要涵盖 整个 字符串 s的&＃xff0c;而不是部分字符串。

说明:

• s 可能为空&＃xff0c;且只包含从 a-z 的小写字母。
• p 可能为空&＃xff0c;且只包含从 a-z 的小写字母&＃xff0c;以及字符 . 和 *。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

方法&＃xff1a;动态规划

思路&＃xff1a;

由于整个字符串是否可以匹配是与子串是否匹配相关的&＃xff0c;因此使用动态规划来解决。

我们使用dp(i,j)表示s的[0,i-1]和p的[0,j-1]两个子串是否匹配&＃xff0c;注意i或j等于0的时候&＃xff0c;表示子串为空串&＃xff0c;所以答案为dp(m,n)。m&＃61;len(s),n&＃61;len(p)。

由于存在&＃39;.&＃39;符号&＃xff0c;可以匹配任意的字符&＃xff0c;所以我们编写一个match(i,j)函数来判断两个字符s[i-1]和p[j-1]是否匹配。如果两个字符相等&＃xff0c;或者p[j-1] &＃61; &＃39;.&＃39;&＃xff0c;那么返回True。如果i&＃61;0或者j&＃61;0&＃xff0c;那么相当于此时为空字串&＃xff0c;不存在s[i-1]或p[j-1]&＃xff0c;所以返回False。

下面我们考虑状态转移方程&＃xff1a;

当遍历到i&＃xff0c;j时&＃xff0c;如果此时p[j-1]不为&＃39;&＃39;&＃xff0c;那么意味着不需要考虑 的情况&＃xff0c;只需要考虑match(i,j)&＃xff0c;转移方程为&＃xff1a;

如果此时的p[j-1]为&＃39;&＃39;&＃xff0c;那么需要考虑匹配情况&＃xff0c;我们把符号 和它前面的符号当作一个整体。如果此时s[i-1]与p[j-2]不匹配&＃xff0c;即match(i,j-1)&＃61;False&＃xff0c;比如下图这种情况&＃xff1a;

此时b和c不相等&＃xff0c;说明此时的这个 符号是无效的&＃xff0c;因为它只能当作一个或多个b&＃xff0c;所以我们把这个 * 当作“0个”的意思&＃xff0c;把这整个&＃39;b*符号去掉&＃xff0c;结果就是蓝色部分匹配的结果&＃xff0c;即dp(i,j-2)。

如果此时s[i-1]与p[j-2]匹配&＃xff0c;那么实际上是有两种情况的&＃xff0c;一种如下图所示&＃xff0c;按照我们理解&＃xff0c;这种情况下这个 实际可以匹配多个b&＃xff0c;但是我们直接枚举的话&＃xff0c;比较耗时&＃xff0c;我们充分发挥动态规划的优点&＃xff0c;直接结果为dp(i-1,j)即可&＃xff0c;因为dp(i-1,j)中就已经包含了这个 匹配前面的b的情况了。

另一种情况如下所示&＃xff0c;此时&＃39;b*&＃39;并没有什么用&＃xff0c;因此可以与上面一样&＃xff0c;当作0个的意思&＃xff0c;所以为dp(i,j-2)。

因此如果p[j-1]为&＃39;*&＃39;&＃xff0c;状态转移方程为&＃xff1a;

下面我们考虑边界条件&＃xff0c;首先如果s和p都为空&＃xff0c;那么为True&＃xff0c;故dp(0,0)&＃61;True&＃xff0c;如果p为空&＃xff0c;那么都为False&＃xff0c;所以我们初始化dp数组的时候&＃xff0c;全部初始化为False&＃xff0c;然后dp(0,0) &＃61; True&＃xff0c;遍历的时候&＃xff0c;i取值[0,m]&＃xff0c;j取值[1,n]。

最后返回dp[m] [n]即可。

结果&＃xff1a;