动规训练四:Leetcode 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
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 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 198.大家劫舍

动归训练二:Leetcode 54. 最大子序和

动规训练三:Leetcode 322. 零钱兑换

发表评论

后才能评论