本题和leetcode10.正则表达式类似，本站也有关于第10题的题解。相比于第十题，本地的情况少一些，更加简单。

题目

https://leetcode.cn/problems/wildcard-matching/

给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

  • '?' 可以匹配任何单个字符。
  • '*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

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 = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：
输入：s = "cb", p = "?a"
输出：false
解释：'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

提示：

1
2
3
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成

思路

本题的星号独立存在，不再像第十题一样是和前一个匹配符绑定的了。所以最终的情况就少了一些。下面的题解是基于第十题之上进行的修改。

本题可以用动态规划的思路，先定义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字符串中删除，此时能否匹配就取决于dp[i][j-1]是否为真了。
  • 当我们匹配1个字符的时候，就相当于使用星号匹配了s[i-1]，此时能否继续匹配就取决于dp[i-1][j]是否为真了。

思考匹配和不匹配时需要沿用哪一个dp结果，可以走这个思路：我们不使用当前的星号进行匹配的时候，相当于从p里面删除当前p[j-1]星号，所以结果是dp[i][j-1]（j前一位，i不变）；如果我们使用当前星号进行匹配，就相当于从s中删除s[i-1]，所以结果是dp[i-1][j]（i前一位，j不变）；

代码

最终的完整代码如下所示

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
class Solution {
public:
    bool isMatch(string s, string p) {
        vector<vector<bool>> dp(s.size() + 1,
                                vector<bool>(p.size() + 1, false));
        // 初始化
        dp[0][0] = true;
        // 初试化
        for (size_t j = 1; j < dp[0].size(); j++) {
            // 如果是*则可以匹配，只要有不是*的就没办法匹配
            dp[0][j] = p[j - 1] == '*' && dp[0][j - 1];
            // cout << j << " " << dp[0][j] << endl;
        }

        // 本题和leetcode10有些区别。主要在于*的处理。
        // 1.字符串是?可以匹配一个
        // 2.字符串是字母，直接比较
        // 3.字符串是*，不需要和前一个配对，直接进行比较
        //      1）匹配0个，则相当于当前字符不存在，沿用dp[i][j-1]
        //      2）匹配1个，相当于?，直接进行匹配，沿用dp[i-1][j]
        //      3）匹配2个以上，不存在这种情况。
        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. '*'只匹配0个字符（相当于删除*）
                    bool result1 = dp[i][j - 1];
                    // 2. '*'匹配1个字符。
                    bool result2 = dp[i - 1][j];
                    // 3. '*'匹配2个和以上的字符
                    //    这种情况不用考虑！因为每次dp循环s只新增了一个字符，那里来的两个字符以上的匹配？

                    // 最终dp只要有一个情况为true就行
                    dp[i][j] = result1 || result2;
                }
                // 情况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

这里顺带给出降重成一维数组之后的代码，合并了部分状态的判断。

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
class Solution {
public:
    bool isMatch(string s, string p) {
        // 降重
        vector<bool> dp(p.size() + 1, false);
        // 初始化
        dp[0] = true;
        // 初试化
        for (size_t j = 1; j < dp.size(); j++) {
            // 如果是*则可以匹配，只要有不是*的就没办法匹配
            dp[j] = p[j - 1] == '*' && dp[j - 1];
        }

        // 本题和leetcode10有些区别。主要在于*的处理。
        // 1.字符串是?可以匹配一个
        // 2.字符串是字母，直接比较
        // 3.字符串是*，不需要和前一个配对，直接进行比较
        //      1）匹配0个，则相当于当前字符不存在，沿用dp[j-1]
        //      2）匹配1个，相当于?，直接进行匹配，沿用dp[j]
        //      3）匹配2个以上，不存在这种情况。
        for (size_t i = 1; i <= s.size(); i++) {
            // 用于保存上一轮 dp 的状态
            bool prev = dp[0];
            dp[0] = false;

            for (int j = 1; j <= p.size(); j++) {
                bool temp = dp[j]; // 保存当前 dp[j]，用于下一次迭代
                if (p[j - 1] == '*') {
                    dp[j] = dp[j - 1] || dp[j]; // 匹配 0 个或 1 个字符
                } else {
                    dp[j] = prev && (p[j - 1] == '?' || s[i - 1] == p[j - 1]);
                }
                prev = temp; // 更新 prev
            }
        }

        return dp[p.size()];
    }
};

image.png