带通配符的模式匹配问题（支持贪婪量词 ' ' 和 '+' 以及懒惰量词 ' ?' 和 '+?' 的进阶版本） 题目描述 给你一个字符串 s 和一个模式串 p ，模式串中包含以下特殊字符： '?' ：匹配任意单个字符。 '*' （贪婪）：匹配任意长度（包括零长度）的字符序列，且尽可能多地匹配字符（贪婪）。 '+' （贪婪）：匹配至少一个任意字符，且尽可能多地匹配字符（贪婪）。 '*?' （懒惰）：匹配任意长度（包括零长度）的字符序列，但尽可能少地匹配字符（懒惰）。 '+?' （懒惰）：匹配至少一个任意字符，但尽可能少地匹配字符（懒惰）。 你需要判断字符串 s 是否完全匹配模式串 p 。 示例： 输入： s = "aaa" , p = "a*" → 输出： true （ '*' 贪婪匹配 "aaa" ） 输入： s = "aaa" , p = "a*?" → 输出： true （ '*?' 懒惰匹配 "" ，但剩下的 "aaa" 无法匹配，因此实际上需要匹配 "aaa" 才能完成匹配，这里 '*?' 在整体匹配时会尝试最小匹配，但最终必须匹配整个 s ，所以会匹配 "aaa" ） 输入： s = "aa" , p = "a+?" → 输出： true （ '+?' 懒惰匹配至少一个 'a' ，这里匹配一个 'a' ，剩下 'a' 需要后续模式匹配） 解题思路 这是一个 区间动态规划 问题，我们可以定义状态 dp[i][j] 表示 s 的前 i 个字符（ s[0:i] ）是否匹配 p 的前 j 个字符（ p[0:j] ）。 i 的范围是 0 到 len(s) ， j 的范围是 0 到 len(p) 。 初始状态： dp[0][0] = true （空串匹配空模式）。 我们需要考虑模式串 p 中的每个字符，特别是特殊量词（ '*' , '+' , '*?' , '+?' ）需要处理其 贪婪 与 懒惰 性质。 状态转移细节 我们按 j 从 1 到 len(p) 进行遍历，对每个 j 考虑 p[j-1] （即当前模式字符）： 1. 普通字符或 '?' 如果 p[j-1] 是普通字符或 '?' ，则： 当 i > 0 且（ s[i-1] == p[j-1] 或 p[j-1] == '?' ）时， dp[i][j] = dp[i-1][j-1] 。 2. 贪婪量词 '*' '*' 表示匹配零个或多个任意字符，且 贪婪 （尽可能多匹配）。 它可以匹配零个字符： dp[i][j] = dp[i][j-1] （跳过 '*' ）。 它可以匹配一个或多个字符：如果 i > 0 且 dp[i-1][j] 为真（即 s[0:i-1] 已经匹配到当前 '*' ），那么 s[i-1] 可以被这个 '*' 匹配，所以 dp[i][j] = true 。 因此转移方程为： dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j]) 3. 贪婪量词 '+' '+' 表示匹配至少一个任意字符，且贪婪。 它不能匹配零个字符，所以必须匹配至少一个字符。 如果 i > 0 且 dp[i-1][j-1] 为真（即 s[0:i-1] 匹配 p[0:j-1] ），那么 s[i-1] 可以作为 '+' 的第一个匹配字符，并且 '+' 可以继续匹配更多字符（因为贪婪），所以 dp[i][j] = dp[i-1][j] （继续用同一个 '+' 匹配）。 同时，如果 i > 0 且 dp[i-1][j] 为真，那么 s[i-1] 可以被这个 '+' 继续匹配。 因此转移方程为： dp[i][j] = (i > 0 && dp[i-1][j-1]) || (i > 0 && dp[i-1][j]) 4. 懒惰量词 '*?' '*?' 匹配零个或多个字符，但 懒惰 （尽可能少匹配）。 它可以匹配零个字符： dp[i][j] = dp[i][j-1] （跳过 '*?' ）。 它可以匹配一个字符：如果 i > 0 且 dp[i-1][j-1] 为真，那么 s[i-1] 可以被 '*?' 匹配，且之后不再匹配更多字符（因为懒惰，匹配一个就停止）。 注意：懒惰匹配在整体匹配中会尝试最小匹配，但必须保证后续模式能匹配剩余字符串。因此，我们需要在状态转移中体现“尽可能少匹配”的语义，这通常可以通过 先尝试匹配零个字符 来实现。即优先考虑 dp[i][j-1] ，如果不行再尝试匹配一个字符。 因此转移方程为： dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j-1]) 5. 懒惰量词 '+?' '+?' 匹配至少一个字符，但懒惰。 它不能匹配零个字符，所以必须匹配至少一个字符。 由于懒惰，它只匹配 恰好一个字符 （如果可能），然后停止。 因此转移方程为： dp[i][j] = i > 0 && dp[i-1][j-1] 算法步骤 初始化 dp[0][0] = true 。 对于 j 从 1 到 len(p) ： 预处理：如果 p[j-1] 是 '*' 或 '*?' ，且 dp[0][j-1] 为真，则 dp[0][j] = true （这些量词可以匹配空串）。 对于 i 从 1 到 len(s) ： 对于 j 从 1 到 len(p) ： 根据 p[j-1] 的类型，应用上述状态转移方程。 最终答案： dp[len(s)][len(p)] 。 示例推导（以 s="aaa" , p="a*?" 为例） 初始化： dp[0][0]=true 。 预处理空串匹配： p[0]='a' 不是量词， dp[0][1]=false ； p[1]='*?' 可以匹配空串，所以 dp[0][2] = dp[0][1] = false 。 逐步计算： i=1, j=1 ： p[0]='a' 匹配 s[0]='a' → dp[1][1] = dp[0][0] = true 。 i=1, j=2 ： p[1]='*?' ： 匹配零个字符： dp[1][1] = true → dp[1][2] = true 。 i=2, j=1 ： p[0]='a' 匹配 s[1]='a' → dp[2][1] = dp[1][0] = false 。 i=2, j=2 ： p[1]='*?' ： 匹配零个字符： dp[2][1] = false → 不成立。 匹配一个字符： i>0 && dp[1][1] = true → dp[2][2] = true 。 i=3, j=1 ： p[0]='a' 匹配 s[2]='a' → dp[3][1] = dp[2][0] = false 。 i=3, j=2 ： p[1]='*?' ： 匹配零个字符： dp[3][1] = false 。 匹配一个字符： i>0 && dp[2][1] = false → dp[3][2] = false 。 最终 dp[3][2] = false ？这与预期 true 不符！ 问题出在哪里？ 关键点 ：懒惰匹配 '*?' 在整体匹配中，虽然尝试最小匹配，但为了匹配整个字符串，它可能需要匹配多个字符。上述转移方程中， '*?' 只允许匹配 零个或一个字符 ，但实际可能需要匹配多个字符才能让后续模式匹配剩余字符串。 修正懒惰量词的转移方程 对于懒惰量词 '*?' ： 它可以匹配零个字符： dp[i][j] = dp[i][j-1] 。 它可以匹配一个字符，并 继续用同一个 '*?' 匹配更多字符 （因为虽然懒惰，但为了整体匹配成功，可能需要匹配多个字符）。 所以： dp[i][j] = dp[i][j] || (i > 0 && dp[i-1][j]) 。 类似地，对于懒惰量词 '+?' ： 它必须匹配至少一个字符。 匹配一个字符后，可以继续匹配更多字符： dp[i][j] = (i > 0 && dp[i-1][j-1]) || (i > 0 && dp[i-1][j]) 。 修正后的转移方程汇总： '*' （贪婪）： dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j]) '+' （贪婪）： dp[i][j] = (i > 0 && dp[i-1][j-1]) || (i > 0 && dp[i-1][j]) '*?' （懒惰）： dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j]) '+?' （懒惰）： dp[i][j] = (i > 0 && dp[i-1][j-1]) || (i > 0 && dp[i-1][j]) 注意： '*' 和 '*?' 的转移方程 相同 ， '+' 和 '+?' 的转移方程 相同 。这是因为在动态规划中，我们是从左到右匹配，贪婪和懒惰的差异体现在 匹配顺序 上，而我们的状态转移已经覆盖了所有可能匹配的字符数，因此最终结果会自动选择能够整体匹配成功的路径。 重新推导示例 s="aaa" , p="a*?" 初始化： dp[0][0]=true 。 预处理： dp[0][1]=false , dp[0][2]=dp[0][1]=false 。 计算： i=1, j=1 ： p[0]='a' → dp[1][1]=dp[0][0]=true 。 i=1, j=2 ： p[1]='*?' → dp[1][2] = dp[1][1] || (1>0 && dp[0][2]) = true || false = true 。 i=2, j=1 ： p[0]='a' → dp[2][1]=dp[1][0]=false 。 i=2, j=2 ： p[1]='*?' → dp[2][2] = dp[2][1] || (2>0 && dp[1][2]) = false || true = true 。 i=3, j=1 ： p[0]='a' → dp[3][1]=dp[2][0]=false 。 i=3, j=2 ： p[1]='*?' → dp[3][2] = dp[3][1] || (3>0 && dp[2][2]) = false || true = true 。 最终 dp[3][2] = true ，匹配成功。 复杂度分析 时间复杂度：O(m × n)，其中 m = len(s) , n = len(p) 。 空间复杂度：O(m × n)，可优化到 O(n)（只保留上一行）。 核心要点 贪婪量词和懒惰量词在动态规划中的转移方程可以相同，因为动态规划会探索所有匹配可能性。 关键是将匹配过程分解为：匹配零个字符（如果允许）或匹配一个字符并继续用同一个量词匹配。 预处理空串匹配时，只有 '*' 和 '*?' 可以匹配空串。 通过以上步骤，你可以判断任意字符串 s 是否匹配包含贪婪/懒惰量词的模式串 p 。