带通配符的字符串匹配问题（支持 '?' 和 '* ' 以及字符类 '[ abc]' 和否定类 '[ !abc]'） 问题描述 给定一个字符串 s 和一个模式串 p ，其中 p 可能包含以下特殊字符： '?' ：可以匹配任意 单个 字符。 '*' ：可以匹配任意长度的字符序列（包括空序列）。 '[abc]' ：可以匹配字符 'a' 、 'b' 或 'c' 中的任意一个。 '[!abc]' ：可以匹配 不在 'a' 、 'b' 、 'c' 中的任意单个字符。 问：模式串 p 是否能够完全匹配字符串 s ？ 示例： s = "aab" , p = "c*a*b" → 输出 false （因为 'c' 开头无法匹配）。 s = "aab" , p = "a*?" → 输出 true （'* ' 匹配 "ab"，'?' 匹配 'b'）。 s = "abc" , p = "a[bc]c" → 输出 true （'[ bc ]' 匹配 'b'）。 s = "abc" , p = "a[!b]c" → 输出 false （'[ !b ]' 不能匹配 'b'）。 解题思路 这是一个经典的字符串匹配问题，可以通过区间动态规划（本质上是一个二维 DP）解决。我们定义状态 dp[i][j] 表示：字符串 s 的前 i 个字符（即 s[0..i-1] ）是否与模式串 p 的前 j 个字符（即 p[0..j-1] ）匹配。目标是求 dp[m][n] ，其中 m = s.length() , n = p.length() 。 状态转移步骤 初始化 dp[0][0] = true ：空字符串匹配空模式。 对于模式开头的连续 '*' ，因为 '*' 可以匹配空序列，所以如果 p 的前 k 个字符都是 '*' ，则 dp[0][k] = true （表示空字符串可以被这些模式匹配）。 状态转移 （考虑 s 的第 i 个字符 s[i-1] 和模式 p 的第 j 个字符 p[j-1] ） 如果 p[j-1] 是普通字符（不是特殊字符）： 只有当 s[i-1] == p[j-1] 且 dp[i-1][j-1] == true 时， dp[i][j] = true 。 如果 p[j-1] 是 '?' ： 可以匹配任意单个字符，所以只要 dp[i-1][j-1] == true ， dp[i][j] = true 。 如果 p[j-1] 是 '*' ： 有两种情况使 dp[i][j] = true ： a) '*' 匹配空序列： dp[i][j-1] == true （即不使用 '*' ）。 b) '*' 匹配当前字符 s[i-1] 并继续匹配： dp[i-1][j] == true （即使用 '*' 匹配当前字符，并保留 '*' 以便继续匹配更多字符）。 如果 p[j-1] 是 '[' （表示字符类的开始）： 需要找到对应的 ']' 作为字符类的结束，然后检查 s[i-1] 是否在字符类内（或对于否定类是否不在类内）。 假设字符类为 p[j-1..k] ，其中 p[k] == ']' 。 如果字符类以 '!' 开头（例如 "[!abc]" ）： 当 s[i-1] 不在字符类中且 dp[i-1][k] == true 时， dp[i][k+1] = true （注意：匹配完整个字符类后，模式指针应跳到 k+1 ）。 否则（例如 "[abc]" ）： 当 s[i-1] 在字符类中且 dp[i-1][j-1] == true 时， dp[i][k+1] = true 。 因为字符类可能包含多个字符，我们需要提前解析模式串，记录每个 '[' 对应的 ']' 位置，以便在 DP 时直接跳转。 优化细节 解析字符类：可以预处理一个数组 matchClass[j] ，表示当 p[j] 是 '[' 时，对应的 ']' 的位置。 对于否定类，检查字符不在类中时，要注意转义字符（本问题不涉及转义）。 由于 '*' 可以匹配任意序列，如果模式中有多个连续的 '*' ，可以合并为一个 '*' 以优化。 最终答案 dp[m][n] 即为结果。时间复杂度 O(m × n)，空间复杂度 O(m × n)（可优化到 O(n)）。 示例验证 以 s = "abc" , p = "a[bc]c" 为例： dp[1][1] = true （'a' 匹配 'a'）。 遇到 '[' ，字符类为 "[bc]" ，匹配到 'b' ， dp[2][4] = true （跳过字符类）。 最后 'c' 匹配 'c' ， dp[3][5] = true ，所以完全匹配。