题目链接：44.通配符匹配

题解：

又是一道关于正则表达式匹配问题的，和上一道10.正则表达式匹配几乎类似！

同样的做法，再来一次动态规划！

题目简述：

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

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

很明显，这个定义和正则的含义不尽相同，没关系，根据题意来就行了。

题解：

同样使用闫式DP分析法：

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

如下图，由于我写过了一遍，就不再写了！

状态转移方程如下：

当p[j] != '*' f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '?')

当 p[j] == '*' f[i][j] = f[i][j - 1] || i && f[i - 1][j] （添加 i 防止越界）

注意点：

  1. 初始状态f[0][0] = true
  2. j从0开始无意义，因为非空串无法匹配空串
  3. 第一个if同样需要防止越界
  4. 最终答案为f[n][m]
  5. 将字符串从0开始，可以省去边界情况的处理

时间复杂度：O(n * m)

AC代码：

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(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 - 1] || i && f[i - 1][j];
                }
            }
        }
        return f[n][m];
    }
};