通配符匹配—动态规划

发布: 分类: 评论次数： 阅读次数： 本文字数： 2.8k

今天要记的题目是关于动态规划的两道题，没错，两道题，因为很类似，所以就放一起记了

相信很多人应该都有类似的感觉（卧槽，原来是这样的嘛？这递推公式也不怎么难嘛—做题前；额，，额，这递推公式咋想啊～—做题时）。动态规划，主要的在于当你拿到一道题时，要能想到使用动态规划（很多情况，我都是直接硬怼，递归走起，结果不是超时就是错误），其次是能够将问题的细节想明白，将流程中的一小步拿出来单独去看，最后，将这一小步写成递推公式

第一道题

题目介绍

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

1
2
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
1
2
3
4
5
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
1
2
3
4
5
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

思路

首先看题，无非是字符串之间的匹配，只是加入了两种符号而已～

注意：为解释方便，都默认目前模式串的匹配位置为p[j]，即第j+1个字符（从1开始），主串的匹配位置为s[i]，在这两个位置前的均已匹配成功

最直接的想法：分情况讨论（p[j]的分类）

  • p[j]为a-z间的字符的时候，直接匹配即可，如果p[j] != s[i]，直接false，反之j++，i++
  • p[j]为’?’符号的时候，表示可以匹配任何单个字符，因此，不用看，直接i++，j++
  • p[j]为’*’符号的时候，表示可以匹配任何字符串（注意：这里是与下一道题不同的地方），到这里，就属于比较麻烦的情况了，因为我们不知道这个符号代替的到底是什么？空串？单字符？还是多字符？都有可能，因此继续分情况讨论
    • 如果是空串，就看p[j+1]与s[i]的关系
    • 如果是单字符呢，就直接看p[j+1]与s[i+1]的关系
    • 最麻烦的是多字符，这个时候，仔细想下，多字符？也就是说除了当前s[i]这个字符外，p[j]还会匹配s[i]后面的字符，所以就继续看p[j]与s[i+1]的关系

这就是最直接的思路，也就是递归的思路，不过这个思路中，存在大量的重复计算，导致无法AC，实际上，加上一个用来记忆判断过的下标组合就可以AC，这里就不贴代码了，因为这不是我想要记录的部分(>^ω^<)

递归加记忆化可以通过的题，动态规划怎么可能不行呢？肯定是可以的，常规操作，构建dp数组，dp[i] [j]表示的是指p的前j个字符与s的前i个字符的匹配与否（注意：dp[2] [3]意思是p[2]与s[1]前面的匹配情况，包括p[2]和s[1]）

数组定义好后，需要将一些边界关系设置好，比如，dp[0] [0] = true，dp[?] [0] = false (? > 0)，dp[0] [?]则需要人为判断下，因为只有当p的前?个字符都是’*’才可以为true

边界关系设置好后，就是递推公式的推导，这也是最烦的地方，一步步来看：

  • 当p[j]为a-z字符时，dp[i+1] [j+1] = dp[i] [j] && (p[j] == s[i]) （这很容易懂吧～，就是说，是字符的话，就看p[j]和s[i]前面的匹配与否与p[j]，s[i]是否相等共同决定）
  • 当p[j]为’?’时，dp[i+1] [j+1] = dp[i] [j]
  • 当p[j]为’*’时，也是比较麻烦，分情况讨论：
    • ‘*’表示多字符时，dp[i+1] [j+1] = dp[i] [j+1]. 可以看出来，这里的想法和递归刚好是相反的，递归的时候，多字符我们是向后看的，但是这里，我们是往前看的，也就是说这个多字符包含的是前面的字符加上当前字符
    • ‘*’表示单字符时，dp[i+1] [j+1] = dp[i] [j].
    • ‘*’表示空串时，dp[i+1] [j+1] = dp[i+1] [j]

实际上，对’*’的分类可以更简单点，两种：使用与未使用，使用了的话，dp[i+1] [j+1] = dp[i] [j+1]；没使用的话，dp[i+1] [j+1] = dp[i+1] [j]

可能到这，还是有点懵，没事，再简单点来说，首先明确一点，动态规划是根据前面的状态来考虑后面的状态，因此，不用去想p[j]后面的匹配情况。假设我们使用了*号，那么我们是不是无法确定目前的s[i]是代表的多字符的最后一个？因此，需要查看s[i-1]的情况，也就是dp数组中的dp[i] [j+1]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public boolean isMatch(String s, String p){
    int len1 = s.length();
    int len2 = p.length();

    if(len1==0 && len2==0){
        return true;
    }

    boolean[][] dp = new boolean[len1+1][len2+1];
    dp[0][0] = true;
    for(int i=1;i<=len2;i++){
        if(p.charAt(i-1)=='*'){
            dp[0][i] = true;
        }else {
            break;
        }
    }

    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(p.charAt(j-1)=='?'){
                dp[i][j] = dp[i-1][j-1];
            }else if(p.charAt(j-1)=='*'){
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            }else{
                dp[i][j] = (s.charAt(i-1)==p.charAt(j-1)) && dp[i-1][j-1];
            }
        }
    }
    return dp[len1][len2];
}

第二道题

题目介绍

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

  • '.' 匹配任意单个字符
  • '*' 匹配零个或多个前面的那一个元素

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

1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
1
2
3
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
1
2
3
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

老实说，就是第三个示例让我很迷糊～导致这道题我一直没做，直到把上面那道题做完了后才回去看的这道题

思路

这道题肯定也是有很多思路的啦，比如递归啥的，，只是这里就只讲下动态规划的思路，便于我自己记忆（没错！！我自己～）

与上面那道题的不同在于，这里的’*’号不是可以代替任意字符串的，它必须有个前缀字符，并且其作用是将前缀字符重复任意次，简单点来说，a *就是指可以表示空串，aa，aaa等

那么，这会造成什么不一样的呢？其实区别也不是太大，往下看就知道了～

首先构建dp数组，定义与上面那道题一样

接着，边界有点变化，dp[0] [?]的判断不太一样，这里，如果希望是true，那么p必须类似于a * a* a*这种，而且？必须是 *号下标才可以，那这该怎么弄呢？别忘了，我们这是动态规划，是有前面的状态的，没错，dp[0] [i] 与dp[0] [i-2]是有关系的（当然，仅在p[i-1]为 * 号的时候）

最后就是递推公式，大体上与上道题类似，只是些许不同

  • 当p[j] 为a-z字符时，dp[i+1] [j+1] = dp[i] [j] && (p[j] == s[i])
  • 当p[j] 为 ‘.’时，dp[i+1] [j+1] = dp[i] [j]
  • 当p[j] 为 ‘*’时，分类讨论：
    • 使用了 *号：dp[i+1] [j+1] = dp[i] [j+1]. (理由与上道题是相同的，当前s中的字符不一定是 *号代表的最后一个字符，我们不向后看)
    • 没使用 *号：dp[i+1] [j+1] = dp[i+1] [j-1] 注意

标注的注意的地方，也就是与上道题不同所在，因为这里的 *号始终是与前面那个字符是绑定的，因此不用的话前面那个字符也被删掉，所以减了2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean isMatch(String s, String p){
    int len1 = s.length();
    int len2 = p.length();

    if(len1==0 && len2==0){
        return true;
    }

    boolean[][] dp = new boolean[len1+1][len2+1];
    dp[0][0] = true;

    for(int i=1;i<=len2;i++){
        if(p.charAt(i-1)=='*'){
            dp[0][i] = dp[0][i-2];
        }
    }

    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(p.charAt(j-1)=='*'){
                  if(p.charAt(j-2)==s.charAt(i-1) || p.charAt(j-2)=='.'){
                      dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];   //匹配多字符  匹配一个字符  匹配空字符
                  }else{
                      dp[i][j] = dp[i][j-2];
                  }
            }else if(p.charAt(j-1)=='.'){
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = (p.charAt(j-1)==s.charAt(i-1)) && dp[i-1][j-1];
            }
        }
    }
    return dp[len1][len2];
}

结束

到这里，关于这两道动态规划的题就结束了，不过很大可能，下次遇到，我还是，，呵呵，你懂的

至于番剧嘛，在追了在追了，对了，不得不吹下斗破的三年之约是真的好看（可能有人会说，好看，我看你只是馋女王的身子～）么的错！！好看的都是我老婆～

我就问，这腰谁不喜欢～～～