LeetCode 10. Regular Expression Matching
2020-06-02 17:18:53 # leetcode # core problems # dynamic programming

Problem

LeetCode 10. Regular Expression Matching

1. 题目简述

给出两个字符串s和p，其中s是由小写字母组成，p是由小写字母以及’.’和’*‘组成，’.’和’*‘分别有如下含义：

'.' 可以表示任何单个字符
'*' 可以表示0个或者多个*前面的字符（需要组合起来看，例如:'a*'可以表示0个a或者多个a）

例如：

Example 1:
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input:
s = "aa"
p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

2. 算法思路

相关问题：

  1. LeetCode 44. Wildcard Matching
  2. “LeetCode 72. Edit Distance”

这种题就是做过一次才能有大概思路，也不能保证完全能做出来。

动态规划

首先，对于这道题，直接用动态规划分析，没有为什么。分析p的两种特殊字符，比较麻烦的是’*’，因为我们不知道它会代表几个字符。因此我们只能逐个分析，代表0个，1个……

这里latex写公式有点问题，因此主体逻辑在注释中，其实其中最难理解的部分就是p[j]为’*’时的情况。

这里我们将其分为两种子情况：

  1. s[i] 和 p[j - 1]不匹配：那么dp[i][j] = dp[i][j - 2]，这是因为既然二者不匹配的话，说明只能将dp[j - 1]dp[j]这个小pattern当做是空串；

  2. s[i] 和 p[j - 1]匹配：这里我们再去分析其可能的情况。匹配0个s[i]，1个s[i]，2个s[i]……但是我们仔细一想可以发现，假如说匹配2个及以上个s[i]的话，那么s的前i-1个字符的子串和p的前j个字符的子串也一定是匹配的！这里以两个为例:

    s:”acbbbd”
    p:”acb*d”

当i = 3时，也就是计算s的子串”acbb”时，当我们匹配到j = 3时，也就是说”acb*”时，我们发现”acb*”和i = 2时的”acb”也是匹配的，因为这里”b*”表示为1个b。换句话说，如果”b*”表示两个及以上的“b”的话，那么s[0， i-1]和p[0, j]也一定是匹配的，因为”b*”表示的重复有很多。

因此对于上面的情况2，我们可以将匹配2个及以上s[i]的情况递推为dp[i - 1][j]，因此我们有递推式：

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

三项分别对应0个，1个和多个的情况。

进一步，我们可以将其规约为两项，因为如果*的前一个字符和s[i]相匹配，那么可以匹配0个，1个，2个，3个…对于1个及以上的情况，我们可以将其规约到dp[i-1][j+1]里面，因为这次的的1个,2个,3个等于上次匹配的0个,1个，2个…

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

参考解析：LeetCode discussion区的大佬解法

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public boolean isMatch(String s, String p) {
        // 这里s和p可能都为空
        if (s == null || p == null) {
            return false;
        }

        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m+1][n+1];
        dp[0][0] = true;
        char[] s_char = s.toCharArray();
        char[] p_char = p.toCharArray();


        // 初始化
        for (int i = 0; i < n; i++) {
            if (p_char[i] == '*') {
                // 相当于中间要跨一个格子，例如s=“”，p="a#b#"
                dp[0][i+1] = dp[0][i-1];
            }
        }

        // 开始dp
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 二者正常匹配，无#情况
                if (p_char[j] != '*') {
                    if (s_char[i] == p_char[j] || p_char[j] == '.') {
                        dp[i + 1][j + 1] = dp[i][j];
                    }
                    continue;
                }

                // 如果p[j]=='*'，分情况讨论
                if (p_char[j - 1] != s_char[i] && p_char[j - 1] != '.') {
                    // *的前一个字符不匹配，那么只能当做匹配0个处理了
                    dp[i+1][j+1] = dp[i+1][j-1];
                } else {
                    // *的前一个字符和s[i]相匹配，那么可以匹配0个，1个，2个，3个...对于1个及以上的情况，我们可以将其规约到dp[i-1][j+1]里面，因为这次的的1个,2个,3个等于上次匹配的0个,1个，2个...
                    dp[i+1][j+1] = dp[i+1][j-1] || dp[i][j+1];
                }
            }
        }

        return dp[m][n];
    }
}

Prev
2020-06-02 17:18:53 # leetcode # core problems # dynamic programming
Next