# \[44]\[困难]\[动态规划]\[背包] 通配符匹配

## 题目描述

[44. 通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/)

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '\*' 的通配符匹配。

'?' 可以匹配任何单个字符。 '\*' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。

说明:

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

## 解题思路

### 动态规划

[通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode-solution/)

这道题本质上是一个**01背包**问题.

将待匹配字符串`s`中的每一个字符视为物品, 每个物品只能使用一次, 去填入它可以对应的字符模式串`p`中的字符. 因此字符模式串`p`就是本题的背包. 只是这个背包有些特殊, 它不是按大小容量来限制, 而是要从左到右按顺序填满, 并且其中每个字符的`容量`还不同. 状态矩阵`dp[i][j]`代表着将`p`中的前i个字符与`s`的前j个字符, 能够匹配.

字母只能匹配相同字母的位置, 只能且必须匹配一个, `?`可以匹配任意字母, 也是只能匹配一个, 且必须匹配一个, `*`可以匹配任意字母, 可以匹配0到无数个字符元素.

根据上面的条件写出字符模式串中不同元素对应的状态转移公式.

另外需要注意初始化. 对应`dp[i][0]`不能再像传统的背包问题全部置为`True`了. `p`中的前i个字符可以与空字符串匹配的条件是, `p[:i + 1]`中的字符都是`*`. 因此将`dp[0][0]`初始化置为`True`后, 再将`p`中前面为`*`的位置初始化为`True`, 遇到第一个非`*`字符停止, 后面的初始化为`False`.

与通用的背包问题不同, 这里要考虑模式串`p`的每个位置, 不同的模式字符对应着不同的状态转移方程. 具体参考[通配符匹配](https://leetcode-cn.com/problems/wildcard-matching/solution/tong-pei-fu-pi-pei-by-leetcode-solution/).

```python
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n, m = len(s), len(p)
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = True  # 空字符串和空模式串匹配
        for i in range(m):  # 模型串前i个字符如果都为*, 则对应位置的dp为True
            t_pattern = set(list(p[:i + 1]))
            if len(t_pattern) == 1 and '*' in t_pattern:
                dp[0][i + 1] = True
            else:
                break

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if p[j - 1] == '?':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                else:
                    dp[i][j] = dp[i - 1][j - 1] and s[i - 1] == p[j - 1]
        return dp[-1][-1]
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/44-tong-pei-fu-pi-pei.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.