动规训练四：Leetcode 10. 正则表达式

五大算法思想 0 2.4K

题目描述

给你一个字符串 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
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

输入：s = "mississippi" p = "mis*is*p*."
输出：false

提示：

0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

题解

这道题有一定难度，题解写了好几个小时，感觉不大好讲，不过我们还是按照我们说的动态规划三部曲来，没看过的看我之前写的文章：告别动态规划，谈谈我的一些经验

一、定义数组的含义

字符串问题，90% 可以用动态规划来解决，对于这种有两个字符串的，基本都是二维数组来存放，我们定义 dp[i] [j] 的含义是当字符串 s 的长度为 i，模式串 p 的长度为 j 时，两者是否匹配，那么 dp[len_s] [len_p] 就是我们要的答案了。

注：len_s 表示字符串 s 的长度，len_p 表示 p 的长度。

二、找出数组元素之间的关系式

在比较字符的过程中，由于 p[j] 有三种类型的字符：.，*和普通字符，分以下情况讨论

1、当 p[j] 为 “.” 或者普通字符：这种情况比较简单，直接与 s[i] 进行匹配：

1）如果匹配成功，那么就继续往下匹配，则有 dp[i] [j] = dp[i-1] [j-1]

2）如果匹配不成功，则有 dp[i] [j] = false。

2、如果 p[j] 为 * 时，稍微复杂一些，这里我们假设 p[j] 前面的一个字符是 b，即

p[j-1] = 'b';p[j] = '*'; // 主要是为了方便讲解

分如下情况讨论

（1）因为 * 可以代表 0 个或多个前面的字符，所以我们必须要考虑他前面的元素 p[j-1]。因为 * 是跟着他前一个字符走，前一个能匹配上 s[i]，* 才能有用，前一个都不能匹配上 s[i]，* 也无能为力，只能让前一个字符消失，也就是匹配 0 次前一个字符，这里相当于把 p[j] 和 [j-1] 两个字符b*都被删除了，那么有 dp[i] [j] = dp[i] [j – 2]。

也就是说，当 p[j-1] != s[i] 时，有 dp[i] [j] = dp[i] [j – 2]。

（2）另一种就是当 p[j-1] = = s[i] 时，那么还会有如下三种情况：

1). 当 * 匹配 0 个字符时：其实和上面情况类似，相当于 p[j] 和 [j-1] 两个字符b*都被删除了，那么有 dp[i] [j] = dp[i] [j – 2]。，

2). 当 * 匹配 1 个时：如果只匹配了一个，即 p[j] 和 [j-1] 两个字符b* 变成了一个字符 b，这是相当于把 p[i] = * 这个字符删除了，那么有 dp[i] [j] = dp[i] [j-1]。

3). 当 * 匹配多个时：匹配多个时，相当于把 b* 变成了 bb*、bbb*等等，由于 b 是和 s[i] 匹配的，那我们可以拿 b 和 s[i] 相互抵消掉，然后 b* 还是保持原来的模样，和 s 后面的字符继续匹配，相当于把 s[i] 这个字符删除了，原理类似，这时有 dp[i] [j] = dp[i-1] [j]。

所以当 p[j-1] = = s[i] 时，有如下情况：

dp[i][j] = dp[i][j-2] // 匹配 0 个的情况
dp[i][j] = dp[i][j-1] // 单个字符匹配的情况
dp[i][j] = dp[i-1][j] // 多个字符匹配的情况

即

dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]

三、找出数组初始值

初始值还是比较容易找的，当两个字符串都是空字符串时，有 dp[0] [0] = true。

当 s 是空字符，p 不是空字符串时，我们需要判断 p[j] 是否为 *，如果为 *，则 dp[0] [j] = dp[0] [j – 2]。

当 s 不是空字符，p 是空字符串时，则有 dp[i][0] = false。

看代码吧，代码有详细解释

public boolean isMatch1(String s, String p){
       if(s == null || p == null)
           return false;
       int len_s = s.length();
       int len_p = p.length();
       //存放状态，默认初始值都是 false。
       boolean[][]dp = new boolean[len_s+1][len_p+1];
       //初始化
       dp[0][0] = true;
       for(int j = 1; j <= len_p; j++){
           if(p.charAt(j-1) == '*')
               dp[0][j] = dp[0][j-2];
       }
       for(int i = 1; i <= len_s; i++){
           for(int j = 1; j <= len_p; j++){
               //如果不为‘*’且匹配
               if(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1))
                   dp[i][j] = dp[i-1][j-1];
               //如果是 *
               else if(p.charAt(j-1)=='*'){
                   //如果p[j]前面的字符p[j-1]与s[i]字符不匹配，则匹配0个
                   if(j!=1&&p.charAt(j-2)!='.'&&p.charAt(j-2)!=s.charAt(i-1)){
                       dp[i][j] = dp[i][j-2];
                   }else{
                       //否则有三种情况：
                       //匹配0个，匹配1个，匹配多个
                       dp[i][j] = dp[i][j-2] || dp[i][j-1]||dp[i-1][j];
                   }
               }
           }
       }
       return dp[len_s][len_p];
   }

动规训练四：Leetcode 10. 正则表达式

题目描述

题解

相关训练题

发表评论取消回复

题目描述

题解

相关训练题

发表评论 取消回复

发表评论取消回复