区间动态规划例题：带通配符的模式匹配问题（支持 '?' 和 '' 匹配，且 '' 可匹配任意序列（包括空序列），但本题目增加额外条件：'?' 必须匹配恰好一个字符，且匹配的字符序列必须是非空的）

题目描述

我们有两个字符串：一个模式串 pattern 和一个文本串 text。
模式串中可能包含两种特殊字符：

• '?' 可以匹配恰好一个任意字符。
• '*' 可以匹配任意长度（包括长度0） 的任意字符序列（即可以匹配空串、一个字符、多个字符），但在本题的设定中，'*' 不能连续出现（即模式串中不会出现 "**" 这样的连续星号）。

请写一个算法，判断 text 是否与 pattern 完全匹配。
注意：匹配必须是完整的，即 text 的整个字符串必须与 pattern 完全匹配，而不是部分匹配。

示例 1：

• 输入：pattern = "a?b*c", text = "axbxyzc"
• 输出：True
• 解释：'?' 匹配 'x'，'*' 匹配 "bxyz" 中的 "bxyz" 部分，最后 'c' 匹配 'c'，整体完全匹配。

示例 2：

• 输入：pattern = "a*b?c", text = "abc"
• 输出：False
• 解释：'*' 匹配空串，剩下 "b?c" 与 "abc" 匹配，'b' 匹配 'a' 失败。

解题思路

这是一个经典的字符串匹配问题，由于模式串中包含通配符，且匹配具有“任意长度匹配”的特性，适合用区间动态规划（实际上是二维DP，但可视为在 pattern 和 text 上的区间DP）解决。

动态规划状态定义：
设 dp[i][j] 表示模式串的前 i 个字符（pattern[0..i-1]）是否能匹配文本串的前 j 个字符（text[0..j-1]）。

• i 的范围：0 到 m（m 为 pattern 的长度）
• j 的范围：0 到 n（n 为 text 的长度）

初始状态：

• dp[0][0] = True：空模式匹配空文本。
• dp[0][j] = False（j > 0）：空模式无法匹配非空文本。
• dp[i][0]：只有当模式的前 i 个字符全部是 '' 时，才可能匹配空文本（因为 '' 可以匹配空序列）。所以需要特殊处理。

状态转移方程：
考虑当前状态 dp[i][j]，我们需要看 pattern[i-1] 和 text[j-1]：

1. 如果 pattern[i-1] 是普通字符（不是 '?' 也不是 '*'）：
   则必须满足 pattern[i-1] == text[j-1]，并且 dp[i-1][j-1] 为 True，即：

   dp[i][j] = (pattern[i-1] == text[j-1]) and dp[i-1][j-1]
   

2. 如果 pattern[i-1] 是 '?'：
   它可以匹配任意一个字符，所以只要 dp[i-1][j-1] 为 True 即可：

   dp[i][j] = dp[i-1][j-1]
   

3. 如果 pattern[i-1] 是 '*'：
   这里比较关键。'*' 可以匹配任意长度的序列，包括空序列。所以对于 dp[i][j]，我们有两种选择：

   • 匹配空序列：即忽略当前 '*'，看 dp[i-1][j] 是否为 True。
   • 匹配一个或多个字符：即用当前 '' 匹配 text[j-1]，并继续用这个 '' 去匹配更前面的字符（因为 '*' 可以匹配多个，所以模式索引 i 不前进，文本索引 j 前进），即看 dp[i][j-1] 是否为 True。

   因此状态转移为：

   dp[i][j] = dp[i-1][j] or dp[i][j-1]
   

   注意：这里 dp[i][j-1] 表示用当前的 '' 匹配了 text[j-1] 后，'' 还可以继续匹配前面的字符。

最终答案：
dp[m][n] 即为整个模式串是否匹配整个文本串。

详细步骤与示例推导

以示例1：pattern = "a?b*c", text = "axbxyzc" 为例。

1. 初始化：

   • m = 5, n = 7
   • dp[0][0] = True
   • 第一行 dp[0][j] = False（j>0）
   • 第一列：dp[i][0] 只有当模式前 i 个字符全为 '*' 时才为 True。这里 pattern[0]='a'，所以 dp[1][0]=False，后续均为 False。

2. 填表过程：

   • i=1 (pattern[0]='a'):
     j=1 (text[0]='a'): 字符相等，且 dp[0][0]=True → dp[1][1]=True。
     其他 j 均不匹配。

   • i=2 (pattern[1]='?'):
     j=2 (text[1]='x'): '?' 可匹配任意字符，且 dp[1][1]=True → dp[2][2]=True。
     注意：必须 j>=i 才可能匹配，因为 '?' 必须消耗一个字符。

   • i=3 (pattern[2]='b'):
     j=3 (text[2]='b'): 字符相等，且 dp[2][2]=True → dp[3][3]=True。
     其他 j 不匹配。

   • i=4 (pattern[3]=''):
     对于每个 j>=3，我们需要计算 dp[4][j]。
     例如 j=3: dp[4][3] = dp[3][3] or dp[4][2]。dp[3][3]=True，dp[4][2] 未计算但初始为 False → dp[4][3]=True。
     类似地，j=4: dp[4][4] = dp[3][4] or dp[4][3]。dp[3][4]=False，dp[4][3]=True → dp[4][4]=True。
     实际上，一旦 dp[4][3]=True，由于 '' 可以继续匹配后续字符，所以对于所有 j>=3，dp[4][j] 都会为 True（因为 dp[4][j-1] 会递推为 True）。
     所以 dp[4][3] 到 dp[4][6] 均为 True。

   • i=5 (pattern[4]='c'):
     我们只关心 j=7 (text[6]='c')：字符相等，且 dp[4][6]=True → dp[5][7]=True。

3. 最终结果：dp[5][7] = True，匹配成功。

复杂度分析

• 时间复杂度：O(m × n)，需要填充一个 m×n 的 DP 表。
• 空间复杂度：O(m × n)，可以优化为 O(n) 因为每行只依赖上一行和当前行。

代码实现（Python）

def isMatch(pattern: str, text: str) -> bool:
    m, n = len(pattern), len(text)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    # 初始化
    dp[0][0] = True
    for i in range(1, m + 1):
        if pattern[i-1] == '*':
            dp[i][0] = dp[i-1][0]  # 只有前面全是 '*' 才可能匹配空文本
        else:
            break  # 一旦遇到非 '*'，后续 dp[i][0] 都是 False
    
    # 状态转移
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if pattern[i-1] == '*':
                dp[i][j] = dp[i-1][j] or dp[i][j-1]
            elif pattern[i-1] == '?' or pattern[i-1] == text[j-1]:
                dp[i][j] = dp[i-1][j-1]
            # 否则 dp[i][j] = False（默认已为 False）
    
    return dp[m][n]

# 测试
print(isMatch("a?b*c", "axbxyzc"))  # True
print(isMatch("a*b?c", "abc"))      # False

关键点总结

1. 状态 dp[i][j] 表示前缀匹配，不是子序列匹配。
2. '*' 的状态转移是本题核心：dp[i][j] = dp[i-1][j] or dp[i][j-1]，分别对应匹配空序列和匹配当前字符并继续匹配。
3. 初始化时注意：空模式只能匹配空文本；模式前缀全为 '*' 时才能匹配空文本。
4. 本题假设模式串中没有连续 ''，若有连续 '' 可预先合并为一个 '*' 以简化。

这个题目是通配符匹配的基础问题，理解了它就能处理更复杂的正则表达式匹配（如带 '+'、'?' 量词等）的区间动态规划解法。