带通配符的模式匹配问题（'?' 和 '* ' 匹配，进阶：支持字符类 '[ ...]' 和 '!' 取反） 题目描述 给定一个模式串 p 和一个字符串 s ，判断 s 是否与 p 完全匹配。模式串 p 支持以下通配符语法： ? ：匹配任意 一个 字符。 * ：匹配任意 零个或多个 字符序列（包括空序列）。 [...] ：字符类，匹配括号内列出的任意 一个 字符。例如 [abc] 匹配 'a'、'b' 或 'c'。 [!...] ：取反字符类，匹配 不在 括号内列出的任意 一个 字符。例如 [!abc] 匹配除了 'a'、'b'、'c' 之外的任意一个字符。 注意 ： 字符类 [...] 内部不会出现通配符 ? 和 * ，并且不会嵌套。 ! 仅在 [ 后紧跟时才表示取反。 匹配必须覆盖 整个 字符串 s ，而不仅仅是部分子串。 示例： 输入： p = "a[*]b" , s = "acb" -> 输出： True (因为 [*] 是字符类，匹配 'c'，所以整体 "acb" 匹配 "a[* ]b") 输入： p = "a*b"， s = "ab" -> 输出： True (因为 * 匹配零个字符) 输入： p = "a[!bc]d", s = "aed" -> 输出： True (因为 [!bc] 匹配 'e') 输入： p = "a[!bc]d", s = "abd" -> 输出： False (因为 [!bc] 不匹配 'b') 解题思路与过程 这是一个 字符串匹配 问题，但由于模式 p 中的 * 可以匹配任意长度子串，使得匹配具有“跨度”，通常需要使用 动态规划 来解决。我们采用区间DP（更准确地说是二维DP，索引 i 和 j 分别表示字符串和模式的前缀）的思路。 第一步：状态定义 定义 dp[i][j] 为一个布尔值，表示字符串 s 的前 i 个字符（即 s[0..i-1] ）是否与模式 p 的前 j 个字符（即 p[0..j-1] ）匹配。 i 的取值范围是 0 到 len(s) ， j 的取值范围是 0 到 len(p) 。 dp[0][0] 表示空字符串匹配空模式，为 True 。 第二步：状态转移方程（重点与难点） 我们需要根据 p[j-1] （即模式的第 j 个字符）的类型，分类讨论： 情况1： p[j-1] 是一个普通字符（非通配符，且不在字符类括号内） 匹配条件： s 的第 i 个字符必须等于 p 的第 j 个字符，并且前面的部分也要匹配。 转移方程： dp[i][j] = (i > 0 && s[i-1] == p[j-1] && dp[i-1][j-1]) 情况2： p[j-1] 是 '?' '?' 可以匹配任意单个字符，只要 s 还有字符即可。 转移方程： dp[i][j] = (i > 0 && dp[i-1][j-1]) 情况3： p[j-1] 是 '* ' 这是最复杂的情况。 * 可以匹配零个或多个字符。 匹配零个字符：相当于忽略这个 * ，即 dp[i][j] |= dp[i][j-1] 。 匹配一个或多个字符：相当于 * 先匹配掉 s 的最后一个字符 s[i-1] ，然后这个 * 继续可以匹配前面的部分。即 dp[i][j] |= (i > 0 && dp[i-1][j]) 。 综合转移方程： dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j]) 。 情况4： p[j-1] 是字符类的结束符 ']' 当我们遇到 ']' 时，意味着我们正在处理一个字符类 [...] 或 [!...] 。我们需要找到这个字符类的开始位置（即对应的 ' [ '）。 设这个字符类在模式中的起始索引为 k （ p[k] 是 ' [ '）。 那么 p[k..j-1] 就构成了一个完整的字符类描述，例如 [abc] 或 [!xyz] 。 匹配条件： s 必须还有字符（ i > 0 ）。 字符 s[i-1] 必须在该字符类的匹配规则内。 模式中这个字符类之前的部分（ p[0..k-1] ）必须与 s 的前 i-1 个字符（ s[0..i-2] ）匹配。 为了判断条件2，我们需要一个辅助函数 charMatch(charSet, ch) ： 参数 charSet 是字符类的内部字符串（不包括外层的 '[ '、'!' 和 ']'），例如 "abc" 或 !xyz 。 参数 ch 是待匹配的字符。 规则： a. 如果 charSet 以 '!' 开头，则 ch 不能出现在 charSet 的剩余部分中。 b. 否则， ch 必须出现在 charSet 中。 转移方程： dp[i][j] = (i > 0 && charMatch(p, k+1, j-1, s[i-1]) && dp[i-1][k]) 。 这里 charMatch(p, k+1, j-1, s[i-1]) 表示判断 s[i-1] 是否匹配字符类 p[k..j-1] 。注意 p[k] 是 '[ '， p[k+1] 可能是 '!' 或普通字符， p[j-1] 是 ']'，所以内部字符串是 p[(k+1) .. (j-2)] 。 注意 ：在实现时，当 j 指向 ']' 时，我们需要回溯找到对应的 ' [ ' 的位置 k 。这可以在预处理时完成，或者每次在DP循环中向前搜索。 第三步：初始化 dp[0][0] = True ：空字符串匹配空模式。 第一行 dp[0][j] （ j > 0 ）：表示空字符串 s 与非空模式 p 的匹配。 只有模式 p 的前 j 个字符全部是能够匹配空串的字符（即连续的 * ）时，才可能为 True 。 因此，我们可以遍历 p ，如果 p[j-1] 是 * ，则 dp[0][j] = dp[0][j-1] ；否则， dp[0][j] = False 。 第一列 dp[i][0] （ i > 0 ）：表示非空字符串 s 与空模式 p 的匹配。显然，只要 s 非空，就不可能匹配空模式（除非模式是 * ，但空模式没有 * ）。所以 dp[i][0] = False 。 第四步：计算顺序与最终答案 计算顺序：由于 dp[i][j] 可能依赖于 dp[i-1][j-1] （左上）、 dp[i-1][j] （上）、 dp[i][j-1] （左），所以我们按照 i 从 0 到 len(s) ， j 从 0 到 len(p) 的二重循环顺序计算即可。 最终答案： dp[len(s)][len(p)] 表示整个字符串 s 是否与整个模式 p 匹配。 第五步：复杂度分析 时间复杂度：O(m * n)，其中 m = len(s) , n = len(p) 。对于字符类匹配，查找对应的 ' [ ' 可以在O(1)内通过预处理完成，判断字符是否在集合内可以在O(字符集大小)内完成，通常很小，视为常数。 空间复杂度：O(m * n)。可以使用滚动数组优化到 O(n)。 示例推导 以 p = "a[*]b" , s = "acb" 为例： m=3 , n=5 。初始化 dp 表（尺寸 4x6）， dp[0][0]=True 。第一行： p[0]='a' 不是 * ，所以 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状态 j 是索引， p[j-1] 是当前字符。这里 j=2 -> p[1] 是 '[ '，我们将其视为普通字符（它是字符类的开始标记）。但按照我们的定义，字符类的匹配发生在遇到 ']' 时。所以对于 ' [ '，我们暂时将其视为一个必须精确匹配的普通字符。然而在这个模式中，' [ ' 是字符类的一部分，我们不希望它被单独匹配。因此，我们需要调整策略：在预处理时，我们不把 ' [ ' 当作一个需要匹配的独立字符，而是将整个字符类（如 [*] ）视为一个“元字符”。这可以通过在构建DP时，当遇到 '[ ' 时，我们将其与后续的字符（直到 ' ]'）绑定为一个匹配单位。 更简洁的实现方式是：在遍历模式 p 时，当遇到 '[ ' 时，我们找到对应的 ']'，然后将这个区间视为一个整体。但在DP的 j 循环中， j 是逐步增加的，我们需要知道当前位置是否在一个字符类内部。一种常见技巧是 预处理模式 ，将每个字符类替换为一个特殊的“元字符”标记，并记录其匹配规则。但为了清晰，我们可以保持上述的状态转移，在遇到 ']' 时才进行字符类匹配，而 ' [ ' 在DP中作为一个普通字符处理（但实际上，如果模式是 a[*]b ， p[1]='[' 是一个普通字符，那么 s[1] 必须是 ' [ ' 才能匹配，这显然不对）。 正确的处理方法是： 修改状态定义 。 dp[i][j] 中， j 是遍历模式的索引，但当我们处理字符类时，我们需要“消耗”掉整个字符类。这意味着在 j 指向 ']' 时，我们进行匹配，并且状态转移的来源是 dp[i-1][k] ，其中 k 是字符类 ' [ ' 之前的位置。因此，我们不需要为字符类内部的字符（如 '[ '、内部字符、甚至 '!'）单独设置DP状态。我们可以 在预处理阶段将模式中的字符类压缩 为一个特殊的标记节点，并在DP中用一个单独的匹配函数来处理它。但为了教学清晰，我们采用另一种等价方法：在DP循环中，当 p[j-1] 是 ']' 时，我们找到匹配的 ' [ ' 位置 k ，然后判断 s[i-1] 是否匹配这个字符类，并查看 dp[i-1][k] 。而字符类内部的字符不参与独立的DP状态转移（即我们不计算 dp[*][j] 当 p[j-1] 是 ' [ ' 或内部字符时）。这意味着我们需要 跳过字符类内部的索引 。 为了简化，我们可以修改DP循环的遍历方式：不是简单地 j 从1到 n ，而是按“模式单元”推进。但这样实现较复杂。 由于详细实现这种“压缩”会使得讲解冗长，我们可以给出一个 更直接的实现思路 ，它稍微牺牲效率但易于理解： 我们仍然使用 dp[i][j] ， i 范围 [ 0, m]， j 范围 [ 0, n ]。 在循环中，如果 p[j-1] 是 '[ '，我们暂时不处理它（因为它必须和后面的 ']' 一起处理）。但这样 j 就不能顺序增加了。因此，我们需要改变循环方式。 简化实现（不跳过字符类内部） ： 将字符类视为一个整体匹配单元。在DP时，当我们位于字符类的开始 '[ ' 时，我们预期下一个字符是匹配的字符，但 ' ]' 还未出现。这会导致逻辑混乱。 为了避免混淆，我们采用 预处理模式字符串 的方法： 扫描模式 p ，将其转换成一个列表 pattern_units ，其中每个元素要么是单个字符（普通字符、'?'、'* '），要么是一个结构体表示字符类（包含是否取反以及字符集合）。 然后基于 pattern_units 进行DP，定义 dp[i][j] 表示 s 的前 i 个字符是否匹配 pattern_units 的前 j 个单位。 这样，状态转移就变得统一，不再需要特殊处理字符类边界。字符类单位就像一个加强版的 '?'，它匹配特定集合内的一个字符。 限于篇幅，这里不展开预处理后的DP推导，但核心思想不变 ：遇到 '* ' 时有匹配零个或多个两种选择；遇到字符类单位时，检查 s[i-1] 是否在允许集合内；遇到 '?' 匹配任意单个字符；普通字符需相等。 最终答案 是 dp[m][len(pattern_units)] 。 总结 本题是通配符匹配的进阶版，增加了字符类功能。解题关键在于 定义清晰的DP状态 ，并 正确处理 '* ' 的匹配逻辑 （这是通配符匹配的核心）以及 将字符类作为一个整体匹配单元 。通过预处理模式字符串，可以简化DP状态转移。这个题目综合了字符串处理、动态规划和逻辑分类，是区间DP（二维DP）应用的典型例子。