leetcode刷题笔记-10.正则表达式匹配。

2024年秋招柠檬微趣C++开发和B站测开笔试都出现了这道题。

本题和leetcode 44.通配符匹配类似，做完本题后，您可以继续做44题。本站也有关于44题的题解。

题目

https://leetcode.cn/problems/regular-expression-matching/description/

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:
输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：
输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

1
2
3
4
5
1 <= s.length <= 20
1 <= p.length <= 20
s 只包含从 a-z 的小写字母。
p 只包含从 a-z 的小写字母，以及字符 . 和 *。
保证每次出现字符 * 时，前面都匹配到有效的字符

思路

对题目的解释

这道题的描述很烂很烂，主要是关于'*'的描述，说的是“匹配零个或多个前面的那一个元素”。这个描述应该改成“'*'匹配零个前面那一个元素，或多个前面的那一个元素”。

举个例子，当我们有一个匹配字符串p = "ab*"的时候，最后一个*需要和前面的b绑定使用，即"b*"，含义是匹配0个b或者无数个b。而如果匹配字符串是".*"，比如题目里面的示例三，那就是等于有0个'.'或者无数个'.'，相当于可以匹配0个或者无数个随机字符（'.'本身可以匹配任何单个字符，合起来就是随机字符匹配了），所以示例三里面才能匹配上ab。

在题目的提示里面也说到了，保证每次出现*的时候都能匹配到有效的字符，即不可能会出现*之前没有其他字母的情况，也不应该出现两个**连着的情况。

现在我们了解了题目这个令人琢磨不透的描述了，可以来写代码了。

思路说明

本题可以用动态规划的思路，先定义dp数组，用的是非常常见的定义方式，在很多动态规划的题目中都是用这个方式定义的：

  • dp[i][j] 为s中i之前，p中j之前（不包括i、j）的字符串能否匹配成功；
  • 换句话说： dp[i][j]为s中前i个和p中前j个字符能否匹配成功；

根据这个定义，需要将dp数组构建如下

1
2
3
// dp[i][j]代表s中i之前（不包括i）和p中j之前（不包括j）的是否能匹配
vector<vector<bool>> dp(s.size() + 1,
						vector<bool>(p.size() + 1, false));

随后是定义递归方程，分为三种情况：

  • p[j-1]是字母。

这种情况的递归方程比较简单，我们判断s[i-1] == p[j-1]就能知道当前是否能继续往后匹配了。规划方程如下：

1
dp[i][j] = dp[i - 1][j - 1] && s[i - 1] == p[j - 1];

其中dp[i - 1][j - 1]代表的是s中前i-1个字符和p中前j-1个字符是否能成功匹配，是“上一次”计算的结果。

  • p[j-1]是'.'。

这种情况其实和是字母没区别，因为'.'可以当作任意一个字母来判断。规划方程如下

1
dp[i][j] = dp[i - 1][j - 1] && p[j - 1] == '.';
  • p[j-1]是'*'。

此时就需要分类讨论了，分为两种情况

  • 星号和前一个字符配对，一起匹配0个字符；
  • 星号和前一个字符配对，一起匹配1个字符；

理论上来说还会有匹配2个及以上字符的情况，但是我们这里不需要讨论这种情况，因为我们dp数组在单次循环中，s和p里面的字符都是只会增长1个的，只是引入了1个新的字符，那里有匹配俩个及以上字符的情况呢？

当我们匹配0个字符的时候，就相当于是把p[j-1]和p[j-2]从p字符串中删除，此时能否匹配就取决于dp[i][j-2]是否为真了。

当我们匹配1个字符的时候，就需要将p[j-2]和*组成的配对串和s进行比较，分为两种子情况：

  • 当p[j-2]是字符的时候，判断p[j-2]和s[i-1]是否相同，是则沿用dp[i - 1][j]的结果；
  • 当p[j-2]是'.'的时候，不需要判断（用'.'去匹配s[i-1]），沿用dp[i - 1][j]的结果；

这里沿用dp[i-1][j]的原因是，我们当前判断的是匹配串p[j-2]*能否继续于与s[i-1]进行匹配，dp[i-1][j]表示s[0:i-1] 可以与 p[0:j] 匹配（即当前字符匹配完成）。而dp[i-1][j-1]的含义是匹配完毕上一个字符就停下了，和当前需要使用p[j-2]*的情况不符合。

最终p[j-1] == '*'合并起来是三种情况，规划方程如下

1
2
3
4
5
6
7
8
9
10
11
12
13
// 1. 'x*'只匹配0个字符（相当于删除x）
bool result1 = dp[i][j - 2];
// 2.'x*'匹配1个字符，此时需要判断s[i-1]和p[j-2]是否相同。
//    这里判断p[j-2]是判断*前面的那一个字符。
//    注意p[j-2]是'.'的时候和s[i-1]==p[j-2]等价。
bool result2 = dp[i - 1][j] && s[i - 1] == p[j - 2];
// 3. 'x*'匹配一个字符，且p[j-2]是'.'，和情况二等价
bool result3 = dp[i - 1][j] && p[j - 2] == '.';
// 4. 'x*'匹配2个和以上的字符
//    这种情况不用考虑！因为每次dp循环s只新增了一个字符，那里来的两个字符以上的匹配？

// 最终dp只要有一个情况为true就行
dp[i][j] = result1 || result2 || result3;

规划方程有了，下面要做的是初始化了。首先显而易见的是dp[0][0] = true，因为s和p都为空串的时候肯定能匹配成功。

然后就是第一行dp[0]的初始化了，假设我们的输入是s="",p="a*"，这种情况下是能让p成功匹配s的，所以需要对第一行进行初始化。初始化沿用的是p[j-1] == '*'的思路，具体代码如下，说明详见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 初始化，dp[0][0]代表s和p两个都是空，可以匹配。
dp[0][0] = true;
// 继续初始化第一行，只有出现了x*(x是任意字符)的时候才可以匹配空字符串s；
// 这个时候我们相当于使用*的匹配0个前一个字符的功能。
for (size_t j = 2; j < dp[0].size(); j += 2) {
	// 比如'b*'我们就认为是匹配0个b，相当于匹配空串。
	// 此时dp就依赖于dp[0][j-2]是否为true了，即抛弃了'b*'中的b还能不能匹配的上。
	//
	// 注意dp数组的定义是i和j之前的元素是否能匹配，不包括i和j自己！
	// 所以当前我们判断的是p[j-1]，而dp[0][j-2]对应的就是p中下标j-3和j-3之前的字符能否匹配。
	// 而'b*'数组为两个元素，当p[j-1]等于*时（j-1=1，j=2）；
	// j-3是负数，即我们希望判断-1和-1之前的字符串p是否能和s匹配；
	// 这个含义就是空字符串p，所以可以和s匹配的上，此时为true。
	dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
	// 一定要根据dp数组的定义来思考这个问题：
	// 假设j-3=0，这时候的含义就变成了判断下标0和0之前的字符是否能匹配，字符串p不是空串，无法和s匹配上。
}

完整代码

完整代码如下

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
49
50
51
52
53
54
55
56
class Solution {
public:
    bool isMatch(string s, string p) {
        // dp[i][j]代表s中i之前（不包括i）和p中j之前（不包括j）的是否能匹配
        vector<vector<bool>> dp(s.size() + 1,
                                vector<bool>(p.size() + 1, false));
        // 初始化，dp[0][0]代表s和p两个都是空，可以匹配。
        dp[0][0] = true;
        // 继续初始化第一行，只有出现了x*(x是任意字符)的时候才可以匹配空字符串s；
        // 这个时候我们相当于使用*的匹配0个前一个字符的功能。
        for (size_t j = 2; j < dp[0].size(); j += 2) {
            // 比如'b*'我们就认为是匹配0个b，相当于匹配空串。
            // 此时dp就依赖于dp[0][j-2]是否为true了，即抛弃了'b*'中的b还能不能匹配的上。
            //
            // 注意dp数组的定义是i和j之前的元素是否能匹配，不包括i和j自己！
            // 所以当前我们判断的是p[j-1]，而dp[0][j-2]对应的就是p中下标j-3和j-3之前的字符能否匹配。
            // 而'b*'数组为两个元素，当p[j-1]等于*时（j-1=1，j=2）；
            // j-3是负数，即我们希望判断-1和-1之前的字符串p是否能和s匹配；
            // 这个含义就是空字符串p，所以可以和s匹配的上，此时为true。
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
            // 一定要根据dp数组的定义来思考这个问题：
            // 假设j-3=0，这时候的含义就变成了判断下标0和0之前的字符是否能匹配，字符串p不是空串，无法和s匹配上。
        }
        // i从1开始遍历（相当于从s的下标0开始处理）
        for (size_t i = 1; i < dp.size(); i++) {
            for (size_t j = 1; j < dp[i].size(); j++) {
                // 情况1，p[j-1] == '*'
                if (p[j - 1] == '*') {
                    // 1. 'x*'只匹配0个字符（相当于删除x）
                    bool result1 = dp[i][j - 2];
                    // 2.'x*'匹配1个字符，此时需要判断s[i-1]和p[j-2]是否相同。
                    //    这里判断p[j-2]是判断*前面的那一个字符。
                    //    注意p[j-2]是'.'的时候和s[i-1]==p[j-2]等价。
                    bool result2 = dp[i - 1][j] && s[i - 1] == p[j - 2];
                    // 3. 'x*'匹配一个字符，且p[j-2]是'.'，和情况二等价
                    bool result3 = dp[i - 1][j] && p[j - 2] == '.';
                    // 4. 'x*'匹配2个和以上的字符
                    //    这种情况不用考虑！因为每次dp循环s只新增了一个字符，那里来的两个字符以上的匹配？

                    // 最终dp只要有一个情况为true就行
                    dp[i][j] = result1 || result2 || result3;
                }
                // 情况2，p[j-1] == '.' 或者是个字母
                else {
                    // 1. 是一个字母，直接判断二者是否相等
                    bool result1 = dp[i - 1][j - 1] && s[i - 1] == p[j - 1];
                    // 2. 是一个'.'，那和二者相等也是没区别的
                    bool result2 = dp[i - 1][j - 1] && p[j - 1] == '.';
                    dp[i][j] = result1 || result2;
                }
            }
        }
        // 返回右下角的值得到是否完成匹配
        return dp[s.size()][p.size()];
    }
};

image.png