带通配符的模式匹配问题（进阶：支持贪婪量词*和+，以及懒惰量词*?和+?）

问题描述

给定一个输入字符串s和一个模式字符串p，模式串中可能包含以下特殊字符：

• '?'：匹配任意单个字符。
• '*'：贪婪量词，匹配任意多个（包括零个）字符。
• '+'：贪婪量词，匹配至少一个任意字符。
• '*?'：懒惰量词，匹配任意多个（包括零个）字符，但尽可能少地匹配。
• '+?'：懒惰量词，匹配至少一个任意字符，但尽可能少地匹配。

请判断s是否能够被模式p完全匹配（即从s的起始到结束，整个字符串都匹配）。
例如：

• s = "aaa", p = "a*" → 匹配（*贪婪匹配三个a）。
• s = "aaa", p = "a+?" → 匹配（+?懒惰匹配一个a，但需要继续匹配剩余部分直到字符串结束，实际上会匹配三个a）。
• s = "aa", p = "a*?a" → 匹配（*?懒惰匹配零个字符，然后a匹配第一个字符，但第二个a无法匹配？这里需要仔细设计状态转移）。

核心思路

这是一个区间动态规划问题，但通常称为“字符串匹配DP”。我们定义二维DP数组：
dp[i][j] 表示 s 的前 i 个字符（即 s[0:i-1]）是否能与 p 的前 j 个字符（即 p[0:j-1]）匹配。

我们需要处理贪婪量词和懒惰量词的差异：

• 贪婪量词（*, +）：尽可能多地匹配字符。
• 懒惰量词（*?, +?）：尽可能少地匹配字符。

在状态转移时，我们需要记录“匹配了多少个字符”作为状态的一部分，但这会使状态爆炸。一个巧妙的解法是：将贪婪和懒惰量词转化为两种不同的状态转移方向，但通过从后向前匹配或记忆化搜索来处理。

解题步骤详解

步骤1：定义状态

dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配。
i 范围 [0, len(s)]，j 范围 [0, len(p)]。
初始化 dp[0][0] = true，表示空串匹配空模式。

步骤2：处理普通字符和?

• 如果 p[j-1] 是普通字符或 ?：
  • 当 i > 0 且（p[j-1] == s[i-1] 或 p[j-1] == '?'）时，dp[i][j] = dp[i-1][j-1]。

步骤3：处理贪婪量词 * 和 +

1. *（匹配零个或多个）：

   • 情况1：匹配零个字符 → dp[i][j] = dp[i][j-1]。
   • 情况2：匹配一个或多个字符 → 如果 i > 0，dp[i][j] = dp[i-1][j]（这里*继续匹配当前字符，模式索引j不变）。
   • 所以转移方程为：dp[i][j] = dp[i][j-1] or (i > 0 and dp[i-1][j])。

2. +（匹配一个或多个）：

   • 不能匹配零个，所以需要先消耗一个字符，然后当作*处理。
   • 即：如果 i > 0，dp[i][j] = dp[i-1][j-1] or (i > 1 and dp[i-1][j])？
     但更清晰的方法是：先匹配至少一个字符，然后允许匹配更多。
     我们可以这样实现：
     • 首先，+必须匹配至少一个字符，所以必须有 i > 0 且 dp[i-1][j-1] 为真（匹配一个字符，然后模式前进到+之后）。
     • 或者，+匹配了多个字符，那么 dp[i][j] = dp[i-1][j]（当前字符被+匹配，模式索引j不变）。
     • 所以：dp[i][j] = (i > 0 and dp[i-1][j-1]) or (i > 0 and dp[i-1][j])。
   • 但注意：dp[i-1][j-1]表示匹配一个字符后模式前进，这适用于+只匹配一个字符的情况。
     实际上，+等价于 [一个字符] + *，但这里我们直接处理。

步骤4：处理懒惰量词 *? 和 +?

懒惰量词的核心是“尽可能少匹配”，在DP中表现为优先尝试匹配零个字符，如果不行再尝试匹配更多。

1. *?（懒惰匹配零个或多个）：

   • 优先匹配零个字符 → dp[i][j] = dp[i][j-2]？不对，因为*?是两个字符*和?的组合，但在模式中它是一个整体。
   • 实际上，*?是一个元字符。我们可以把它当作*处理，但在状态转移时，优先考虑匹配零个字符的情况。
   • 所以转移顺序应该是：
     • 先尝试匹配零个字符：dp[i][j] = dp[i][j-1]（跳过*?）。
     • 如果不行，再尝试匹配一个或多个字符：dp[i][j] = i > 0 and dp[i-1][j]。
   • 但在DP中，我们按i和j循环，无法直接“先尝试哪个”。因此，我们可以在计算dp[i][j]时，先检查dp[i][j-1]，再检查dp[i-1][j]。

2. +?（懒惰匹配至少一个）：

   • 优先匹配一个字符，然后尽快结束匹配。
   • 所以转移顺序：
     • 先匹配一个字符，然后模式前进：dp[i][j] = i > 0 and dp[i-1][j-1]。
     • 如果不行，再匹配多个字符：dp[i][j] = i > 0 and dp[i-1][j]。

步骤5：整合转移方程

我们可以用记忆化搜索来避免顺序问题。定义函数 match(i, j) 表示 s[i:] 和 p[j:] 是否匹配。

• 如果 j == len(p)：返回 i == len(s)。
• 如果 p[j] 是普通字符或 ?：
  • 如果 i < len(s) 且（p[j] == s[i] 或 p[j] == '?'），返回 match(i+1, j+1)。
  • 否则返回 false。
• 如果 p[j] 是贪婪量词：
  • 如果是 *：
    • 匹配零个字符：match(i, j+1)
    • 或者匹配一个或多个字符：i < len(s) and match(i+1, j)
    • 返回两者的或。
  • 如果是 +：
    • 必须先匹配至少一个字符，所以：i < len(s) and (match(i+1, j+1) or match(i+1, j))。
• 如果 p[j] 是懒惰量词：
  • 如果是 *?：
    • 优先匹配零个字符：match(i, j+1)
    • 如果不行，再匹配一个或多个：i < len(s) and match(i+1, j)
    • 注意：我们需要“优先”，所以可以先检查match(i, j+1)，如果为真直接返回；否则再检查另一个。
  • 如果是 +?：
    • 优先匹配一个字符，然后结束：i < len(s) and match(i+1, j+1)
    • 如果不行，再匹配多个字符：i < len(s) and match(i+1, j)

步骤6：实现细节

• 懒惰量词的“优先”可以通过在递归中先判断匹配零个（或一个）的情况来实现。
• 用二维数组 memo[i][j] 缓存结果，避免重复计算。

步骤7：举例验证

例1：s = "aaa", p = "a*?"

• 从头开始，*?优先匹配零个字符，模式跳到下一个，但后面没有模式了，而s还有字符，不匹配。
• 然后尝试匹配一个字符，i=1,j=0，继续匹配，最终匹配全部字符，成功。

例2：s = "aa", p = "a*?a"

• *?优先匹配零个字符，然后模式剩下a，匹配s的第一个a，然后s剩下a，模式结束，不匹配。
• 尝试匹配一个字符，*?匹配一个a，模式剩下a，匹配s的第二个a，成功。

代码框架（记忆化搜索）

def isMatch(s: str, p: str) -> bool:
    memo = {}
    def dfs(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if j == len(p):
            return i == len(s)
        # 处理量词（两个字符的情况）
        is_quant = j+1 < len(p) and p[j+1] in '*+'
        is_lazy = j+1 < len(p) and p[j+1] == '?'
        if is_quant and is_lazy:
            # 懒惰量词，如 *? 或 +?
            quant = p[j]  # * 或 +
            if quant == '*':
                # *? 优先匹配零个
                if dfs(i, j+2):
                    memo[(i, j)] = True
                    return True
                # 否则匹配一个或多个
                if i < len(s) and dfs(i+1, j):
                    memo[(i, j)] = True
                    return True
            else:  # '+?'
                # +? 优先匹配一个
                if i < len(s) and dfs(i+1, j+2):
                    memo[(i, j)] = True
                    return True
                # 否则匹配多个
                if i < len(s) and dfs(i+1, j):
                    memo[(i, j)] = True
                    return True
            memo[(i, j)] = False
            return False
        elif is_quant:
            # 贪婪量词，如 * 或 +
            quant = p[j]
            if quant == '*':
                # 匹配零个
                if dfs(i, j+1):
                    memo[(i, j)] = True
                    return True
                # 匹配一个或多个
                if i < len(s) and dfs(i+1, j):
                    memo[(i, j)] = True
                    return True
            else:  # '+'
                # 匹配至少一个
                if i < len(s) and dfs(i+1, j+1):
                    memo[(i, j)] = True
                    return True
                if i < len(s) and dfs(i+1, j):
                    memo[(i, j)] = True
                    return True
            memo[(i, j)] = False
            return False
        else:
            # 普通字符或 ?
            if i < len(s) and (p[j] == s[i] or p[j] == '?'):
                memo[(i, j)] = dfs(i+1, j+1)
                return memo[(i, j)]
            memo[(i, j)] = False
            return False
    return dfs(0, 0)

总结

本题是带通配符和量词的模式匹配问题的进阶版，关键在于区分贪婪和懒惰量词的匹配策略，在状态转移时通过优先顺序实现。采用记忆化搜索可以更自然地处理这种“优先尝试”，最终时间复杂度为O(nm)，空间复杂度O(nm)。