带通配符的模式匹配问题（'?'和'*'匹配）

题目描述

给定一个字符串 s 和一个模式串 p，模式串中可能包含两种通配符：

• '?' 可以匹配任意单个字符
• '*' 可以匹配任意长度的字符序列（包括空序列）

需要判断字符串 s 是否与模式串 p 完全匹配。

示例

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

解题思路

这个问题可以使用区间动态规划来解决。我们定义 dp[i][j] 表示字符串 s 的前 i 个字符是否与模式串 p 的前 j 个字符匹配。

详细步骤

1. 状态定义

   • dp[i][j]：s 的前 i 个字符（s[0...i-1]）与 p 的前 j 个字符（p[0...j-1]）是否匹配
   • i 的范围：0 到 len(s)，j 的范围：0 到 len(p)

2. 初始化

   • dp[0][0] = true：两个空字符串匹配
   • 对于第一行（s 为空字符串）：
     • 如果 p 的前 j 个字符都是 '*'，那么 dp[0][j] = true
     • 否则为 false
   • 对于第一列（p 为空字符串）：
     • 只有当 s 也为空时才匹配，所以 dp[i][0] = false（i > 0）

3. 状态转移方程

   考虑当前字符的匹配情况：

   • 如果 p[j-1] 不是通配符：
     • 当 s[i-1] == p[j-1] 时，dp[i][j] = dp[i-1][j-1]
   • 如果 p[j-1] 是 '?'：
     • '?' 可以匹配任意单个字符，所以 dp[i][j] = dp[i-1][j-1]
   • 如果 p[j-1] 是 '*'：
     • '*' 可以匹配空序列：dp[i][j-1]
     • '*' 可以匹配一个或多个字符：dp[i-1][j]
     • 所以 dp[i][j] = dp[i][j-1] || dp[i-1][j]

4. 计算顺序

   • 按行从上到下，按列从左到右计算

5. 最终结果

   • dp[len(s)][len(p)]

完整代码实现

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
    
    # 动态规划
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if p[j-1] == '?' or s[i-1] == 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]
    
    return dp[m][n]

示例验证

以 s = "adceb", p = "ab" 为例：

1. 初始化后，dp[0][0] = true，dp[0][1] = true（因为 p[0] = '*'）

2. 逐步计算：

   • 当 i=1, j=1：'*' 匹配 "a" → dp[1][1] = true
   • 当 i=1, j=2：'a' 匹配 'a' → dp[1][2] = dp[0][1] = true
   • 当 i=2, j=2：'d' 不匹配 'a' → false
   • 当 i=2, j=3：'*' 匹配 "d" → dp[2][3] = dp[2][2] or dp[1][3] = false or false = false
   • ...继续计算直到得到最终结果 true

复杂度分析

• 时间复杂度：O(m × n)，其中 m 是 s 的长度，n 是 p 的长度
• 空间复杂度：O(m × n)，可以使用滚动数组优化到 O(n)

这个算法能够有效处理包含通配符的模式匹配问题，通过动态规划逐步构建匹配关系。