带通配符的模式匹配问题（'?' 匹配任意单个字符，'*' 匹配任意字符序列（包括空序列），且支持字符类 '[abc]' 匹配指定字符集合中的任意一个字符）
题目描述
给定一个字符串 s 和一个模式串 p，模式串中可能包含以下特殊字符：
'?'：可以匹配任意单个字符。'*'：可以匹配任意字符序列（包括空序列）。'[abc]'：字符类，可以匹配字符 'a'、'b' 或 'c' 中的任意一个。字符类中不包含特殊字符（如'*','?','[',']'），且不会嵌套（如'[[a]]'不会出现）。
请实现一个函数，判断字符串 s 是否与模式串 p 完全匹配（即整个 s 必须被 p 完全覆盖，不能有多余字符，除非 '*' 匹配了空序列使得模式消耗完但字符串还有剩余是不允许的）。
示例
输入：s = "abcde", p = "a?c*[de]"
输出：true
解释：'a' 匹配 'a'，'?' 匹配 'b'，'c' 匹配 'c'，'' 匹配空序列，'[de]' 匹配 'd' 或 'e'，这里匹配了 'd'，但字符串剩余 'e' 未被匹配，所以不匹配？等等，这里我们仔细分析：模式串最后一个 [de] 匹配了 'd'，但字符串还有一个 'e' 剩余，模式串已结束，所以不匹配。实际上，模式串中的 '*' 可以匹配任意字符序列，包括多个字符。所以正确匹配是：'a' 匹配 'a'，'?' 匹配 'b'，'c' 匹配 'c'，'' 匹配 "de"（两个字符），此时模式串 '*' 后的 [de] 就没有字符可匹配了，所以不匹配？这取决于 '*' 的贪婪性。实际上，在标准通配符匹配中，'*' 是匹配任意序列，包括空序列，但必须整个字符串被完全匹配。这里，我们可以让 '*' 匹配 "d"，然后 [de] 匹配 'e'，这样整个字符串被匹配完。所以是匹配的。
为了清晰，我们明确：匹配必须覆盖整个字符串 s，并且模式串 p 必须消耗完（除了 '*' 可以匹配空序列外，但模式串的每个字符都要参与匹配决策）。
解题过程
这是一个字符串匹配问题，由于模式串包含通配符和字符类，我们可以使用动态规划（DP）来解决。定义状态，然后根据模式字符的类型进行状态转移。
步骤1：定义状态
定义 dp[i][j] 表示：字符串 s 的前 i 个字符（即 s[0..i-1]）是否与模式串 p 的前 j 个字符（即 p[0..j-1]）匹配。
i的取值范围是0到len(s)，j的取值范围是0到len(p)。- 当
i=0且j=0时，表示空字符串匹配空模式，为真。 - 当
i=0但j>0时，表示空字符串匹配非空模式，此时只有模式串全部由可以匹配空序列的'*'组成时才可能为真。 - 当
i>0且j=0时，表示非空字符串匹配空模式，为假。
步骤2：初始化
dp[0][0] = True：空匹配空。- 对于
j从1到len(p)：
如果p[j-1] == '*'，则dp[0][j] = dp[0][j-1]（因为'*'可以匹配空序列，所以如果前j-1个模式能匹配空串，那么前j个也能）。
否则，dp[0][j] = False。 - 对于
i从1到len(s)：dp[i][0] = False（空模式无法匹配任何非空字符串）。
步骤3：状态转移
我们从 i=1 到 len(s)，j=1 到 len(p) 进行遍历。设当前字符为 s[i-1] 和 p[j-1]。
根据 p[j-1] 的类型分为几种情况：
-
如果
p[j-1]是普通字符（即不是'?'、'*'或'['）：
则只有当s[i-1] == p[j-1]且dp[i-1][j-1]为真时，dp[i][j]才为真。
即：dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1])。 -
如果
p[j-1]是'?'：
它可以匹配任何单个字符，所以只要dp[i-1][j-1]为真，dp[i][j]就为真。
即：dp[i][j] = dp[i-1][j-1]。 -
如果
p[j-1]是'*'：
它可以匹配任意字符序列，包括空序列。因此有两种可能性：'*'匹配空序列：此时相当于忽略'*'，看s[0..i-1]是否与p[0..j-2]匹配，即dp[i][j-1]。'*'匹配一个或多个字符：此时'*'匹配了s[i-1]，然后这个'*'还可以继续匹配前面的字符，所以看s[0..i-2]是否与p[0..j-1]匹配，即dp[i-1][j]。
所以：dp[i][j] = dp[i][j-1] or dp[i-1][j]。
-
如果
p[j-1]是'['：
注意，字符类是以'['开头，以']'结尾的，比如[abc]。在模式串中，这样的字符类被视为一个整体。也就是说，当我们处理到p[j-1]是'['时，我们需要找到与之匹配的']'，假设这个字符类是从索引j-1到k-1（包含两端），那么我们需要检查s[i-1]是否在这个字符类的字符集合中，并且如果dp[i-1][j-1]为真，则dp[i][j]可以为真。但注意，在DP表中，我们通常希望每个模式字符对应一列，所以更好的方法是在预处理时，将整个字符类作为一个模式“字符”来处理。为了简化，我们可以在遍历时，如果发现
p[j-1] == '['，则找到对应的']'的位置close，然后取出字符类中的字符集合。然后检查s[i-1]是否在该集合中，并且dp[i-1][j-1]为真。但注意，此时模式消耗了一个字符类（多个字符），所以下一个状态应该是dp[i-1][j-1]对应上一个字符匹配，但这里我们只消耗一个模式字符（即整个字符类被视为一个单元），所以实际上转移是：
dp[i][j] = dp[i-1][j-1] and (s[i-1] in char_set)，其中char_set是从p[j-1:close]解析出的字符集合。
但这样，在DP表中，字符类占用了多个列，这会导致索引错乱。更好的方法是：在读取模式串时，将每个字符类压缩成一个特殊项，这样模式串的长度就是压缩后的长度。但在DP中，我们可以保持原模式串，但遇到'['时，我们跳转到对应的']'之后。不过，为了状态转移的一致，我们可以将字符类视为一个整体，即匹配一个字符，然后模式索引前进到']'的下一个位置。鉴于实现复杂度，我们可以换一种思路：不将字符类视为多列，而是当处理到
p[j-1]是'['时，我们解析出这个字符类，然后检查s[i-1]是否匹配，然后状态从dp[i-1][j-1]转移。但这样，模式索引j在前进时，应该跳到字符类之后。也就是说，如果我们用dp[i][j]表示匹配了模式的前j个字符（字符类算一个字符），那么我们需要预处理模式串，将字符类提取为单个单元。为了简单起见，我们这里采用的方法是：不改变原模式串，但在DP转移时，当
p[j-1] == '['，我们找到对应的']'的位置close，然后检查s[i-1]是否在p[j:close]中（注意不包含括号），然后如果匹配，则dp[i][j] = dp[i-1][j-1]。但此时，模式串的索引j指向的是'['，下一个字符应该是']'之后的位置，但我们的DP表是按每个字符一列构建的，所以我们需要额外处理：当我们匹配了一个字符类后，实际上模式消耗了从j-1到close的所有字符，所以下一个状态应该是dp[i][close]之类的，这会导致DP表定义混乱。为了简化，我们可以先将模式串进行预处理，将每个字符类替换为一个特殊标记（比如用一个元组存储字符集合），这样模式串的每个元素要么是单个字符，要么是一个字符集合。然后DP的状态转移就统一了：当模式元素是字符集合时，检查
s[i-1]是否在集合中，然后从dp[i-1][j-1]转移。但为了清晰讲解，我们这里采用预处理的方法。
步骤4：预处理模式串
我们将模式串 p 转换为一个列表 pattern，其中每个元素是：
- 单个字符（普通字符、
'?'、'*'），或者 - 一个集合（表示字符类中的字符）。
转换规则：
遍历原模式串 p，
- 如果当前字符是
'['，则找到下一个']'的位置，将括号内的字符放入集合，将集合作为一个元素加入pattern，然后指针跳到']'之后。 - 否则，将当前字符作为一个元素加入
pattern。
例如，p = "a?c*[de]" 转换为：pattern = ['a', '?', 'c', '*', {'d', 'e'}]。
注意：字符类内不会有特殊字符，所以直接取字符即可。
步骤5：调整DP定义
设 m = len(s), n = len(pattern)。
定义 dp[i][j] 表示：s 的前 i 个字符是否与 pattern 的前 j 个元素匹配。
初始化类似：
dp[0][0] = True。- 对于
j从1到n：如果pattern[j-1] == '*'，则dp[0][j] = dp[0][j-1]，否则dp[0][j] = False。 - 对于
i从1到m：dp[i][0] = False。
步骤6：状态转移（预处理后）
遍历 i 从 1 到 m，j 从 1 到 n：
设当前模式元素为 pat = pattern[j-1]。
- 如果
pat == '*'：
dp[i][j] = dp[i][j-1] or dp[i-1][j]。 - 否则如果
pat == '?'：
dp[i][j] = dp[i-1][j-1]。 - 否则如果
pat是一个集合：
dp[i][j] = dp[i-1][j-1] and (s[i-1] in pat)。 - 否则（
pat是普通字符）：
dp[i][j] = dp[i-1][j-1] and (s[i-1] == pat)。
步骤7：最终结果
最终答案为 dp[m][n]，即整个字符串 s 是否与整个模式串 pattern 匹配。
举例验证
以示例 s = "abcde", p = "a?c*[de]" 为例：
预处理后 pattern = ['a', '?', 'c', '*', {'d', 'e'}]，m=5, n=5。
初始化 dp[0][0]=True，第一行：dp[0][1]=False（'a'不是''），dp[0][2]=False，dp[0][3]=False，dp[0][4]=True（因为''可以让dp[0][4]=dp[0][3]=True？不对，dp[0][3]是False，所以dp[0][4]=False。实际上，模式串前4个元素是'a','?','c',''，其中'a'、'?'、'c'都不能匹配空串，所以dp[0][4]应该是False。我们需要重新计算：
dp[0][0]=True
j=1: pat='a'，不是''，dp[0][1]=False
j=2: pat='?'，不是''，dp[0][2]=False
j=3: pat='c'，不是''，dp[0][3]=False
j=4: pat=''，是''，dp[0][4]=dp[0][3]=False
j=5: pat={'d','e'}，不是'*'，dp[0][5]=False。
所以第一行都是False，除了dp[0][0]。
现在填充DP表：
i=1,j=1: pat='a'，s[0]=='a'，dp[1][1]=dp[0][0] and True = True。
i=1,j=2: pat='?'，dp[1][2]=dp[0][1]=False。
i=1,j=3: pat='c'，s[0]!='c'，False。
i=1,j=4: pat='*'，dp[1][4]=dp[1][3] or dp[0][4] = False or False = False。
i=1,j=5: pat={'d','e'}，s[0]不在集合，False。
i=2,j=1: pat='a'，s[1]=='b'，不匹配，False。
i=2,j=2: pat='?'，dp[2][2]=dp[1][1]=True。
i=2,j=3: pat='c'，s[1]=='b'，不匹配，False。
i=2,j=4: pat='*'，dp[2][4]=dp[2][3] or dp[1][4] = False or False = False。
i=2,j=5: pat={'d','e'}，s[1]不在集合，False。
i=3,j=1: pat='a'，s[2]=='c'，False。
i=3,j=2: pat='?'，dp[3][2]=dp[2][1]=False。
i=3,j=3: pat='c'，s[2]=='c'，dp[3][3]=dp[2][2]=True。
i=3,j=4: pat='*'，dp[3][4]=dp[3][3] or dp[2][4] = True or False = True。
i=3,j=5: pat={'d','e'}，s[2]不在集合，False。
i=4,j=1: pat='a'，s[3]=='d'，False。
i=4,j=2: pat='?'，dp[4][2]=dp[3][1]=False。
i=4,j=3: pat='c'，s[3]=='d'，False。
i=4,j=4: pat='*'，dp[4][4]=dp[4][3] or dp[3][4] = False or True = True。
i=4,j=5: pat={'d','e'}，s[3]=='d'，在集合中，dp[4][5]=dp[3][4] and True = True and True = True。
i=5,j=1: pat='a'，s[4]=='e'，False。
i=5,j=2: pat='?'，dp[5][2]=dp[4][1]=False。
i=5,j=3: pat='c'，s[4]=='e'，False。
i=5,j=4: pat='*'，dp[5][4]=dp[5][3] or dp[4][4] = False or True = True。
i=5,j=5: pat={'d','e'}，s[4]=='e'，在集合中，dp[5][5]=dp[4][4] and True = True and True = True。
最终 dp[5][5]=True，匹配成功。
复杂度分析
时间复杂度：O(m * n)，其中 m 是字符串长度，n 是预处理后的模式长度。
空间复杂度：O(m * n)，可以优化到 O(n) 因为每行只依赖上一行和当前行。
这个解法逐步处理了通配符和字符类，通过预处理简化了字符类的匹配，使得DP转移统一清晰。