题目链接：10.正则表达式匹配

题解：

又是一道很难的动态规划题，或许他不难，只是我遇到动态规划的题太少了罢了！

历时很久才将其看懂：还是 y 总牛逼！

题目简述：

正则匹配：处理两个字符* 和 .

*：表示0个或多个

.：任意一个字符

给一个字符串，给一个正则，检查能否匹配。

题解：

使用闫式Dp分析法：（集合的方式）

再字符串前面加一个空格，使子符串从1开始！

分为状态表示和状态计算：

  1. 转态表示：两个字符串，则使用两维数组f[i][j] ，来表示原串和正则串的 [1, i] 个 和 [1, j] 个是否匹配，存储的是bool值（表示是否存在一个合法方案，由于*的原因导致方案不唯一）。
  2. 状态计算：（分为两种情况）
    1. p[j] != '*'：则f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == .)
    2. p[j] == '*'：则f[i][j] = f[i][j-2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')

详细解释一下：

1、p[j] != '*'：s串的前 i 个和 p串的前 j个字符f[i][j] 的情况有两个因素确定：

  • f[i - 1][j - 1]：即去除s串的最后一个待匹配字符与p串的最后一个待匹配字符后，要保证前 i - 1和 前 j - 1 个字符匹配
  • (s[i] == p[j] || p[j] == ‘.’)：并且s 串和p串的最后一个字符匹配，或者s串任意字符，p串为 .（匹配任意字符）

2、p[j] == '*'：s串的前 i 个和 p串的前 j个字符f[i][j] 的情况有两个因素确定（（1）即 *表示的个数：0，1，2，3… （2）s与p串尾部的匹配工作）：

  • 0个：f[i][j - 2]
  • 1个：f[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')
  • 2个：f[i - 2][j - 2] && (s[i] == p[j - 1] && s[i - 1] == p[j - 1] || p[j - 1] == '.')
  • …
  • 最后是否匹配即上面有一个成立即可

合并起来看一下： f[i][j] = f[i][j - 2] || f[i - 1][j - 2]&&(s[i] == p[j - 1] || p[j - 1] == '.') || f[i - 2][j - 2] && (s[i] == p[j - 1] && s[i - 1] == p[j - 1] || p[j - 1] == '.') .........

无穷无尽 …

所以咱们来看一下： f[i - 1][j]，同理*号可以取0，1，3，4，5…

最后合并起来就是：f[i - 1][j] = f[i - 1][j - 2] || f[i - 2][j - 2] && (s[i - 1] == p[j - 1] || p[j - 1] == '.') || f[i - 3][j - 2] && (s[i - 1] == p[j - 1] && s[i - 2] == p[j - 1] || p[j - 1] == '.') ..............

观察两个式子，会发现存在一个关系：

f[i][j]包含了f[i - 1][j]：f[i][j] = f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')

这就是状态转移方程！

**注意：**相当于乘法分配律：（A || B）&& C == A && C || B && C，所以可以提出来公共项：(s[i] == p[j - 1] || p[j - 1] == '.')

将上诉关系放到代码框内方便查看：

1
2
3
4
5
6
7
8
9
10
11
12
13
- 0个：`f[i][j - 2]`
- 1个：`f[i - 1][j - 2] && (s[i] == p[j - 1] || p[j - 1] == '.')`
- 2个：`f[i - 2][j - 2] && (s[i] == p[j - 1] && s[i - 1] == p[j - 1] || p[j - 1] == '.')`
- ......

// f[i][j]
f[i][j] = f[i][j - 2] || f[i - 1][j - 2]&&(s[i] == p[j - 1] || p[j - 1] == '.') || f[i - 2][j - 2] && (s[i] == p[j - 1] && s[i - 1] == p[j - 1] || p[j - 1] == '.') .......

// f[i - 1][j]
f[i - 1][j] = f[i - 1][j - 2] || f[i - 2][j - 2] && (s[i - 1] == p[j - 1] || p[j - 1] == '.') || f[i - 3][j - 2] && (s[i - 1] == p[j - 1] && s[i - 2] == p[j - 1] || p[j - 1] == '.') .......

// 最终状态转移方程：
f[i][j] =  f[i][j - 2] || f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.')

AC代码：

这里说一下细节处理：

  1. f[0][0] = true：初始值，两个串的前0个都是空格，匹配。
  2. j = 1开始：j从0开始无意义，从0开始的话，一个非空的串是不可能匹配一个空串 如：f[1][0]。也可以从0开始，但是得防止下标越界问题，不如直接从1开始。
  3. i 从 0 开始：i 可以从 0 开始，s为空格，p为 .* ，即f[0][1]
  4. i == 0：需要特殊判断，i && p[j] != '*'，这个条件得保证i != 0，以防下标越界
  5. j不需要考虑越界问题：j的取值可能在else if下越界，但是，如果走到else if，j 的下标一定大于等于3，即p串至少也是a*，前面再加上初始空格，一定大于等于3，不会发生越界！
  6. s 与 p 串都加一个空格：这样f[0][0]是可以确定的！不加空格，无法有一个初始值。可能会更加复杂！

最后答案就是： f[n][m]即 s 整个串和 p 整个串匹配！

注意：vector<vector<bool>> f(n + 1, vector<bool>(m + 1));，初始化了一个 (n + 1 )* (m + 1)二维数组，默认为false。

详细代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        f[0][0] = true;
        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                if (j + 1 <= m && p[j + 1] == '*') continue;
                if (i && p[j] != '*') {
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }
        return f[n][m];
    }
};