通配符匹配（Wildcard Matching）

题目描述
给定一个字符串 s 和一个模式 p，判断 s 是否与模式 p 完全匹配。
模式 p 中可能包含以下两种通配符：

• ? 可以匹配任意单个字符。
• * 可以匹配任意字符序列（包括空序列）。
  匹配必须覆盖整个输入字符串（而不是部分）。

示例
输入: s = "aa", p = "a"
输出: false
解释: "a" 无法匹配整个 "aa"。

输入: s = "cb", p = "?a"
输出: false
解释: '?' 匹配 'c'，但 'a' 不匹配 'b'。

输入: s = "adceb", p = "ab"
输出: true
解释: 第一个 '' 匹配空序列，第二个 '' 匹配 "dce"。

解题思路
这是一个字符串匹配问题，由于 * 可以匹配任意长度的序列，因此不能简单按字符比较。动态规划是常用的解决思路。

定义状态
设 dp[i][j] 表示字符串 s 的前 i 个字符（s[0..i-1]）和模式 p 的前 j 个字符（p[0..j-1]）是否匹配。
这里 i 和 j 表示长度，取值范围分别为 0..len(s) 和 0..len(p)。

状态转移
我们需要考虑 p[j-1] 的字符类型：

1. 如果 p[j-1] 是普通字符（不含通配符）：
   则 dp[i][j] = (s[i-1] == p[j-1]) && dp[i-1][j-1]。
   即当前字符必须相同，且前面的子串也要匹配。

2. 如果 p[j-1] 是 ?：
   则 dp[i][j] = dp[i-1][j-1]。
   因为 ? 可以匹配任意单个字符，只要前面匹配即可。

3. 如果 p[j-1] 是 *：
   此时 * 可以匹配零个或多个字符。

   • 匹配零个字符：dp[i][j] = dp[i][j-1]（不使用 * 匹配任何字符）。
   • 匹配一个或多个字符：dp[i][j] = dp[i-1][j]（使用 * 匹配当前字符，并继续用 * 匹配前面的字符）。
     综合两种情况：dp[i][j] = dp[i][j-1] || dp[i-1][j]。

初始化

• dp[0][0] = true：空字符串与空模式匹配。
• dp[i][0] = false（i>0）：非空字符串与空模式不匹配。
• dp[0][j]：空字符串只能与模式中连续的 * 匹配。
  即如果 p 的前 j 个字符都是 *，则 dp[0][j] = true，否则一旦遇到非 * 字符，后续全为 false。

最终答案
dp[len(s)][len(p)]。

逐步推导示例
s = "adceb", p = "ab"

1. 初始化 dp 表，行列分别对应 s 和 p 的长度+1。
   dp[0][0] = true。
   第一行 dp[0][j]：检查 p 的前缀是否全为 *。
   p[0]='' → dp[0][1]=true, p[1]='a' 非 '' → 后面全为 false。

2. 填充过程（i 从 1 到 5，j 从 1 到 4）：

   • i=1,j=1: p[0]='*' → dp[1][1] = dp[1][0] || dp[0][1] = false || true = true。
   • i=1,j=2: p[1]='a' ≠ s0? 实际上 s[0]='a' 等于 'a'，但 dp[0][1]=true，所以 dp[1][2]=true。
   • ... 按规则逐步填充，最终 dp[5][4] = true。

代码实现思路

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    dp[0][0] = True
    
    # 初始化第一行
    for j in range(1, n + 1):
        if p[j-1] == '*':
            dp[0][j] = dp[0][j-1]
        else:
            break  # 一旦遇到非 '*'，后面全部为 False（已初始化为 False）
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-1] or dp[i-1][j]
            elif p[j-1] == '?' or s[i-1] == p[j-1]:
                dp[i][j] = dp[i-1][j-1]
    return dp[m][n]

复杂度分析

• 时间复杂度：O(m*n)，其中 m 和 n 分别是 s 和 p 的长度。
• 空间复杂度：O(m*n)，可优化为 O(n) 使用滚动数组。

关键点

• 重点在于 * 的状态转移：匹配零个或多个字符。
• 初始化时，空字符串只与连续的 * 匹配。
• 这个动态规划解法清晰且易于理解，是处理通配符匹配的经典方法。