题目描述

给定一个字符串 s 和一个模式串 p，其中 p 中包含通配符 ? 和 *。

'?' 匹配任意一个字符。
'*' 匹配任意多个字符（包括零个字符）。

说明

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

样例

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

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

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

输入:
s = "acdcb"
p = "a*c?b"
输入: false

算法

(动态规划) $O(nm)$

1. 设状态 $f(i,j)$ 表示 s 串的前 $i$ 个字符与 p 串的前 $j$ 个字符是否匹配。这里的有效下标从 1 开始。
2. 假设 s 串的长度为 $n$，p 串的长度为 $m$。
3. 初始化 $f(0, 0) = true$，其余待定。
4. 转移方程，假设 s 串的第 $i$ 个字符为变量 x，p 串的第 $j$ 个字符为变量 y。

(1) f(i, j) = f(i, j) | f(i - 1, j - 1) 当且仅当 x == y 或 y == '?'。
(2) f(i, j) = f(i, j) | f(i - 1, j) | f(i, j - 1)当且仅当 y == '*'。

解释：

• (1) 的含义是 s 串的第 $i$ 个字符与 p 串的第 $j$ 个字符匹配对应，所以 $f(i,j)$ 的值可以由 $f(i-1,j-1)$ 的值来转移。
• (2) 的含义是，特别地，如果 p 串的第 $j$ 个字符为 *，则可以让 s 串的第 $i$ 个字符同之前的字符串一起（之前的字符串可以为空）与这个 * 对应，或者是 s 串的第 $i$ 个字符与 p 串的第 $j-1$ 个字符对应（* 匹配零个字符）。
• 最终 $f(n, m)$ 的值表示字符串是否匹配。

时间复杂度

• 状态数量为 $O(nm)$，转移时间为 $O(1)$。故总时间复杂度为 $O(nm)$。

空间复杂度

• 需要额外 $O(nm)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.length(), m = p.length();

        vector<vector<bool>> f(n + 1, vector(m + 1, false));

        f[0][0] = true;

        for (int i = 0; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                char y = p[j - 1];
                if (i > 0) {
                    char x = s[i - 1];
                    if (x == y || y == '?')
                        f[i][j] = f[i][j] | f[i - 1][j - 1];
                }
                if (y == '*') {
                    f[i][j] = f[i][j] | f[i][j - 1];
                    if (i > 0)
                        f[i][j] = f[i][j] | f[i - 1][j];
                }
            }

        return f[n][m];
    }
};