区间动态规划例题：正则表达式匹配问题（带通配符和字符类） 题目描述 给定一个字符串 s 和一个模式串 p ，模式串中可能包含以下特殊字符： . 匹配任意单个字符 * 匹配零个或多个前面的元素 [abc] 匹配字符 'a'、'b' 或 'c'（示例字符类） [^abc] 匹配不在 'a'、'b'、'c' 中的任意字符 请实现一个函数，判断字符串 s 是否完全匹配模式串 p 。匹配需覆盖整个字符串 s ，而不仅是部分子串。 示例 输入：s = "aab", p = "c a b" 输出：true（因为 * 可以匹配零个 'c'，然后 "a* b" 匹配 "aab"） 输入：s = "mississippi", p = "mis is p* ." 输出：false 输入：s = "abc", p = "a[ bd ]c" 输出：true（因为 [bd] 匹配 'b'） 解题步骤 1. 定义状态 设 dp[i][j] 表示字符串 s 的前 i 个字符（即 s[0:i-1] ）是否匹配模式串 p 的前 j 个字符（即 p[0:j-1] ）。 注意： i 和 j 表示长度，索引需减1。 2. 初始化边界情况 dp[0][0] = true ：空字符串匹配空模式。 对于 dp[0][j] （即 s 为空但 p 非空）：仅当 p 的某些部分可以匹配空字符串（如 a* 或 [ab]* 等重复模式）时才为 true 。 例如：若 p[j-1] == '*' ，则 dp[0][j] = dp[0][j-2] （跳过前一个字符和 * ）。 3. 状态转移方程 遍历 i 从 1 到 len(s) ， j 从 1 到 len(p) ： 情况1： p[j-1] 是普通字符或 . 若 p[j-1] == s[i-1] 或 p[j-1] == '.' ，则当前字符匹配，状态继承： dp[i][j] = dp[i-1][j-1] 情况2： p[j-1] == '*' 此时需看 p[j-2] （即 * 前面的字符）： 子情况2.1：匹配零次 忽略 p[j-2] 和 * ： dp[i][j] = dp[i][j-2] 子情况2.2：匹配一次或多次 需满足 p[j-2] 匹配 s[i-1] （即 p[j-2] == s[i-1] 或 p[j-2] == '.' ），并且 s 的前缀需匹配当前模式： dp[i][j] = dp[i-1][j] 综合两种情况： dp[i][j] = dp[i][j-2] OR (匹配且 dp[i-1][j]) 情况3： p[j-1] == ']' （字符类结束） 需向前找到匹配的 [ ，检查 s[i-1] 是否在字符类中： 若字符类为 [abc] ，且 s[i-1] 在集合中，则 dp[i][j] = dp[i-1][j-1] 若为 [^abc] ，且 s[i-1] 不在集合中，同样匹配。 注意：字符类可能后跟 * ，需类似情况2处理重复匹配。 4. 处理字符类的预处理 在遍历前，可先解析模式串 p ，将字符类（如 [abc] ）转换为哈希集合，便于快速判断匹配。 5. 最终结果 返回 dp[len(s)][len(p)] ，表示整个 s 是否匹配整个 p 。 举例说明 以 s = "aab" , p = "c*a*b" 为例： 初始化 dp[0][0] = true ， dp[0][2] = true （因为 c* 可匹配空串）。 匹配过程： i=1, j=1 ： p[0]='c' 不匹配 s[0]='a' ，但 j=2 时 p[1]='*' 可跳过 c ，故 dp[1][2]=true 。 后续通过 a* 和 b 逐步匹配完成。 通过逐状态填充，最终得到 dp[3][5] = true 。