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

## 题目描述

[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背包**的衍生问题. 使用的状态是$$ks\[i]\[t]$$, 代表的意义是将前$$i$$个物品放入到一个容量为$$t$$的背包里, 最大的价值. 本题的衍生状态为$$dp\[i]\[j]$$, 表示字符串`s`的前$$i$$个字符和模式串`p`的前$$j$$个字符是否匹配, 布尔值.

与通用的背包问题不同, 这里要考虑模式串`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
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://blessbingo.gitbook.io/garnet/suan-fa/zi-fu-chuan/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.