区间动态规划例题：带通配符的模式匹配问题（支持贪婪量词 ' ' 和 '+' 以及懒惰量词 ' ?' 和 '+?' 的进阶版本） 题目描述 我们给定一个字符串 s 和一个模式串 p ，模式串中可能包含以下字符： 普通字符（小写字母），匹配自身。 通配符 ? ，匹配任意 单个 字符。 通配符 * ，匹配任意 零个或多个 字符序列。 通配符 + ，匹配任意 一个或多个 字符序列。 通配符 *? ，懒惰匹配，匹配任意 零个或多个 字符序列，但尽可能少地匹配字符。 通配符 +? ，懒惰匹配，匹配任意 一个或多个 字符序列，但尽可能少地匹配字符。 问：字符串 s 是否与模式串 p 完全匹配？ 例如： s = "abc" , p = "a?c" → 匹配（ ? 匹配 b ）。 s = "abc" , p = "a*" → 匹配（ * 匹配 "bc" ）。 s = "abc" , p = "a+" → 匹配（ + 匹配 "bc" ）。 s = "abc" , p = "a*?c" → 匹配（懒惰 *? 匹配 "b" 或空字符串，取决于实现，这里通常解释为匹配最少字符，但必须保证整体匹配）。 s = "abc" , p = "a+?c" → 匹配（懒惰 +? 匹配 "b" ，至少一个字符）。 s = "abc" , p = "a*?b" → 不匹配（懒惰 *? 匹配最少字符，但整体无法匹配）。 s = "aa" , p = "a*?" → 匹配（懒惰 *? 匹配零个 a ，但后面无字符，需结合整体检查）。 注意 ：本题要求实现完整的匹配逻辑，包括贪婪量词（ * 和 + ）和懒惰量词（ *? 和 +? ），并且需要精确匹配整个字符串 s 。 解题过程 我们可以用区间动态规划（DP）来解决这个问题。核心思路是定义状态，表示 s 的某个子串是否与 p 的某个子模式匹配，然后通过状态转移逐步推导出整个字符串的匹配情况。 第一步：状态定义 定义 dp[i][j] 为一个布尔值，表示字符串 s 的前 i 个字符（即 s[0:i] ，左闭右开区间）是否与模式串 p 的前 j 个字符（即 p[0:j] ）匹配。 初始状态： dp[0][0] = true ，表示空字符串匹配空模式。 最终目标： dp[n][m] ，其中 n = len(s) ， m = len(p) 。 第二步：初始化 首先，我们需要初始化当 s 为空字符串时的情况。即 dp[0][j] 的值： 如果模式 p 的前 j 个字符能匹配空字符串，则 dp[0][j] = true ，否则为 false 。 具体规则： 如果 p[j-1] 是 * 或 *? ，那么它可以匹配零个字符，所以 dp[0][j] 的值取决于 dp[0][j-1] （即忽略这个量词）。 如果 p[j-1] 是 + 或 +? ，那么它必须匹配至少一个字符，但 s 为空，所以 dp[0][j] = false 。 其他情况（普通字符、 ? 等）都无法匹配空字符串，所以 dp[0][j] = false 。 注意：在处理复合量词如 *? 时，我们将其视为一个整体字符（长度为2的模式字符），但为了方便，我们可以将模式串预处理，将多字符量词视为一个单元。 第三步：状态转移方程 我们按 i 从 1 到 n ， j 从 1 到 m 遍历。设当前考虑 s[i-1] 和 p[j-1] 。 情况1：p[ j-1] 是普通字符 只有当 s[i-1] == p[j-1] 且 dp[i-1][j-1] == true 时， dp[i][j] = true 。 情况2：p[ j-1] 是 '?' 它可以匹配任何单个字符，所以如果 dp[i-1][j-1] == true ，则 dp[i][j] = true 。 情况3：p[ j-1] 是 '* '（贪婪匹配零个或多个） 这里 * 可以匹配零个或多个字符。因此有两种可能性： 匹配零个字符：忽略 * ，即 dp[i][j] = dp[i][j-1] 。 匹配一个或多个字符：让 * 匹配当前字符 s[i-1] ，并继续用 * 匹配前面的字符，即 dp[i][j] = dp[i-1][j] 。 综合： dp[i][j] = dp[i][j-1] or dp[i-1][j] 。 情况4：p[ j-1] 是 '+'（贪婪匹配一个或多个） 类似于 * ，但必须匹配至少一个字符。有两种可能性： 匹配一个字符并结束：即用 + 匹配 s[i-1] 后不再匹配更多，那么需要 dp[i-1][j-1] == true 。 匹配一个字符并继续：用 + 匹配 s[i-1] 后，继续用 + 匹配前面的字符，即 dp[i-1][j] == true 。 注意：不能匹配零个字符，所以没有 dp[i][j-1] 的情况。 综合： dp[i][j] = dp[i-1][j-1] or dp[i-1][j] 。 情况5：p[ j-1] 是 '* ?'（懒惰匹配零个或多个） 懒惰匹配的意思是尽可能少地匹配字符。但为了判断是否匹配，我们需要考虑两种可能性： 匹配零个字符：忽略 *? ，即 dp[i][j] = dp[i][j-2] （注意： *? 是两个字符，所以 j-2 是跳过这两个字符）。 匹配一个字符：让 *? 匹配当前字符 s[i-1] ，然后继续尝试匹配，但此时 *? 可能继续匹配更多字符（但因为是懒惰匹配，我们匹配一个字符后，应尽快结束匹配，将控制权交给下一个模式字符）。所以转移为： dp[i][j] = dp[i-1][j] ？不，这里需要小心。 更准确地说，对于懒惰量词，我们有两种选择： 不匹配任何字符（跳过量词）： dp[i][j] = dp[i][j-2] 。 匹配当前字符，并继续用同一个量词匹配： dp[i][j] = dp[i-1][j] 。 但实际上，对于懒惰匹配，我们优先尝试不匹配任何字符，如果不行再尝试匹配一个字符。但在DP中，我们无法确定“优先”，所以需要同时考虑两种可能性，并用或（ or ）连接。 但注意： *? 是作为一个整体处理的，所以我们用 j 指向 ? 字符（即 p[j-1] == '?' 且 p[j-2] == '*' ），但在实现时，我们可以预处理模式串，将 *? 视为一个特殊字符单元。为简化，我们可以在遍历时检查 p[j-1] == '?' 且 p[j-2] == '*' 来判断是否为 *? ，然后进行相应转移。 假设我们将 *? 视为一个单元，存储在 p 的索引 j-1 处（即 p[j-1] 代表 *? ），那么状态转移为： 匹配零个字符： dp[i][j] = dp[i][j-1] （跳过这个单元）。 匹配一个字符并继续： dp[i][j] = dp[i-1][j] （用 *? 匹配当前字符，并保留 *? 以可能匹配更多字符）。 所以： dp[i][j] = dp[i][j-1] or dp[i-1][j] 。 这看起来和 * 一样？是的，但懒惰匹配和贪婪匹配在匹配行为上不同，但在“是否匹配”这个问题上，只要有一种方式匹配成功即可，所以从匹配结果的角度， * 和 *? 的状态转移方程相同。但如果我们要求匹配的方式（如最少匹配字符数），则会不同。本题只问是否匹配，所以可以简化。 情况6：p[ j-1] 是 '+?'（懒惰匹配一个或多个） 类似于 + ，但尽可能少匹配。状态转移： 匹配一个字符并结束： dp[i][j] = dp[i-1][j-1] （用 +? 匹配当前字符后不再匹配更多）。 匹配一个字符并继续： dp[i][j] = dp[i-1][j] （用 +? 匹配当前字符，并保留 +? 以匹配更多字符）。 所以： dp[i][j] = dp[i-1][j-1] or dp[i-1][j] 。 同样，这与 + 的状态转移方程相同。 重要 ：由于本题只问是否匹配，不关心匹配长度，所以贪婪和懒惰量词在状态转移方程上可以视为相同。但注意初始化时， * 和 *? 可以匹配空串， + 和 +? 不能匹配空串。 第四步：处理多字符量词 在实现时，我们需要将 *? 和 +? 视为一个整体。可以在遍历模式串时，检查当前字符是否为 * 或 + ，且下一个字符是否为 ? ，如果是，则将这两个字符作为一个单元处理。 具体做法： 预处理模式串 p ，将其转换为一个列表 pattern ，其中每个元素是： 单个字符（普通字符、 ? 、 * 、 + ）。 或者双字符单元（ *? 或 +? ）。 这样， dp 的第二维就对应于 pattern 的索引。 为简化，我们也可以不显式预处理，而是在遍历时判断：如果 p[j-1] == '?' 且 j>1 且 p[j-2] 是 * 或 + ，则当前单元是 *? 或 +? ，我们应该将 j 指向这个单元的开始（即 j-2 ）。但这样处理较麻烦，更清晰的方式是预处理。 第五步：算法步骤 预处理模式串 p ，得到列表 pat ，其中每个元素是一个字符或双字符量词。 令 n = len(s) , m = len(pat) 。 初始化 dp 为 (n+1) x (m+1) 的二维布尔数组，全部为 false 。 dp[0][0] = true 。 初始化 dp[0][j] 对于 j=1..m ： 如果 pat[j-1] 是 * 或 *? ，则 dp[0][j] = dp[0][j-1] 。 否则 dp[0][j] = false 。 遍历 i=1..n , j=1..m ： 设 pc = pat[j-1] 。 如果 pc 是普通字符： dp[i][j] = (s[i-1] == pc) and dp[i-1][j-1] 。 如果 pc 是 ? ： dp[i][j] = dp[i-1][j-1] 。 如果 pc 是 * 或 *? ： dp[i][j] = dp[i][j-1] or dp[i-1][j] 。 如果 pc 是 + 或 +? ： dp[i][j] = dp[i-1][j-1] or dp[i-1][j] 。 返回 dp[n][m] 。 第六步：例子验证 以 s = "abc" , p = "a*?c" 为例： 预处理 pat = ['a', '*?', 'c'] ， n=3 , m=3 。 初始化 dp[0][0]=true 。 dp[0][1] : pat[0]='a' 不是 * 或 *? ，所以 false 。 dp[0][2] : pat[1]='*?' 是 *? ，所以 dp[0][2] = dp[0][1] = false 。 dp[0][3] : pat[2]='c' 不是 * 或 *? ，所以 false 。 然后填充 dp ： i=1,j=1 : pc='a' , 匹配 s[0]='a' , dp[1][1] = true 。 i=1,j=2 : pc='*?' , dp[1][2] = dp[1][1] or dp[0][2] = true or false = true 。 i=1,j=3 : pc='c' , 不匹配 'a' , 所以 false 。 i=2,j=1 : pc='a' , 不匹配 'b' , 所以 false 。 i=2,j=2 : pc='*?' , dp[2][2] = dp[2][1] or dp[1][2] = false or true = true 。 i=2,j=3 : pc='c' , 不匹配 'b' , 所以 false 。 i=3,j=1 : pc='a' , 不匹配 'c' , 所以 false 。 i=3,j=2 : pc='*?' , dp[3][2] = dp[3][1] or dp[2][2] = false or true = true 。 i=3,j=3 : pc='c' , 匹配 s[2]='c' , 且 dp[2][2]=true , 所以 dp[3][3]=true 。 结果 dp[3][3]=true ，匹配成功。 第七步：复杂度分析 时间复杂度：O(n × m)，其中 n 为字符串长度，m 为预处理后模式单元的数量。 空间复杂度：O(n × m)，可用滚动数组优化到 O(m)。 总结 这道题是带通配符模式匹配的进阶版，引入了贪婪和懒惰量词。通过区间动态规划，我们能够系统地处理各种匹配规则。关键点在于： 预处理模式串，将多字符量词作为整体处理。 正确推导状态转移方程，特别是量词匹配零个或多个、一个或多个的情况。 初始化时正确处理空字符串的匹配。 这个解法可以扩展到更复杂的正则表达式匹配，是理解正则引擎基础匹配原理的良好练习。