区间动态规划例题：正则表达式匹配问题（支持 '.' 和 '*' 以及 '+' 和 '?' 的量词）
题目描述
给定一个字符串 s 和一个模式串 p，实现支持以下规则的正则表达式匹配：
- '.' 匹配任意单个字符。
- '*' 匹配零个或多个前面的元素。
- '+' 匹配一个或多个前面的元素。
- '?' 匹配零个或一个前面的元素。
匹配应该覆盖整个字符串 s，而不是部分字符串。
你需要判断 s 是否与 p 完全匹配。
例如：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配整个字符串 "aa"。
输入：s = "aa", p = "a*"
输出：true
解释：'*' 表示前面的元素 'a' 重复零次或多次，这里重复两次 "aa"。
输入：s = "ab", p = "."
输出：true
解释："." 表示零个或多个任意字符，可以匹配 "ab"。
输入：s = "aab", p = "cab"
输出：true
解释：c 可以重复零次，a 重复两次，b 匹配 b。
输入：s = "ab", p = "a?b"
输出：true
解释：'?' 表示前面的 a 出现零次或一次，这里出现一次，匹配 "ab"。
输入：s = "aaa", p = "a+"
输出：true
解释：'+' 表示前面的 a 至少出现一次，这里出现三次。
解题思路
本题是经典正则表达式匹配问题的扩展，加入了 '+' 和 '?' 量词。我们可以使用区间动态规划来解决，定义二维 DP 数组，然后根据模式串中的字符和量词，分情况讨论状态转移。
步骤详解
步骤1：定义DP数组
- 定义
dp[i][j]表示：s 的前 i 个字符（s[0..i-1]）与 p 的前 j 个字符（p[0..j-1]）是否匹配。 - 初始时，
dp[0][0] = true，表示空字符串匹配空模式。
步骤2：初始化空模式匹配非空字符串的情况
- 对于
i > 0且j = 0，dp[i][0] = false，因为非空字符串无法匹配空模式。
步骤3：初始化空字符串匹配模式的情况
- 对于
j > 0，即模式非空，需要考虑量词 '*'、'?' 可能表示零个字符的情况，从而让模式匹配空字符串。 - 规则：如果
p[j-1]是 '' 或 '?'，那么dp[0][j]的值取决于dp[0][j-2]（跳过前面的字符和量词），因为 '' 或 '?' 可以匹配零个前面的元素。 - 注意：如果
p[j-1]是 '+'，则不能匹配零个，所以不能匹配空字符串，保持 false。
步骤4：状态转移（填表）
遍历 i 从 0 到 n（n 为 s 长度），j 从 1 到 m（m 为 p 长度），对每个 dp[i][j] 分情况讨论：
-
如果 p[j-1] 是普通字符（不是 '.' 和量词）：
- 则需要 s[i-1] 等于 p[j-1]，且前面的部分匹配，即：
dp[i][j] = (s[i-1] == p[j-1]) && dp[i-1][j-1]。
- 则需要 s[i-1] 等于 p[j-1]，且前面的部分匹配，即：
-
如果 p[j-1] 是 '.'：
- '.' 可以匹配任意单个字符，所以只要前面部分匹配即可：
dp[i][j] = dp[i-1][j-1]。
- '.' 可以匹配任意单个字符，所以只要前面部分匹配即可：
-
如果 p[j-1] 是量词（'*'、'?'、'+'）：
- 量词必须和它前面的字符一起处理，所以我们需要看 p[j-2] 是什么字符（这里 j ≥ 2）。
- 设
prev = p[j-2]（前面的字符）。 - 然后根据量词类型处理：
a) '*' 量词（零个或多个 prev）：
- 两种情况取或：
- 匹配零个 prev：跳过 "prev*"，即
dp[i][j] = dp[i][j-2]。 - 匹配一个或多个 prev：需要当前 s[i-1] 能匹配 prev（即 s[i-1]==prev 或 prev=='.'），并且 s 的前 i-1 个字符能匹配当前模式（即
dp[i-1][j]为真）。
- 匹配零个 prev：跳过 "prev*"，即
- 综合：
dp[i][j] = dp[i][j-2] || ( (s[i-1]==prev || prev=='.') && dp[i-1][j] )。
b) '?' 量词（零个或一个 prev）：
- 两种情况取或：
- 匹配零个 prev：跳过 "prev?"，即
dp[i][j] = dp[i][j-2]。 - 匹配一个 prev：需要当前 s[i-1] 能匹配 prev，且前面部分匹配，即
(s[i-1]==prev || prev=='.') && dp[i-1][j-2]。
- 匹配零个 prev：跳过 "prev?"，即
- 注意：匹配一个时，模式中 "prev?" 消耗了模式的两个字符，所以是
j-2。 - 综合：
dp[i][j] = dp[i][j-2] || ( (s[i-1]==prev || prev=='.') && dp[i-1][j-2] )。
c) '+' 量词（一个或多个 prev）：
- 两种情况：
- 匹配一个 prev：需要当前 s[i-1] 匹配 prev，并且前面部分匹配模式中 "prev+" 之前的部分，即
(s[i-1]==prev || prev=='.') && dp[i-1][j-2]。 - 匹配多个 prev：需要当前 s[i-1] 匹配 prev，并且 s 的前 i-1 个字符能匹配当前模式（即
dp[i-1][j]为真），因为 '+' 表示至少一个，消耗一个后模式不变。
- 匹配一个 prev：需要当前 s[i-1] 匹配 prev，并且前面部分匹配模式中 "prev+" 之前的部分，即
- 注意：这里不能匹配零个，所以没有
dp[i][j-2]。 - 综合：
dp[i][j] = ( (s[i-1]==prev || prev=='.') && (dp[i-1][j-2] || dp[i-1][j]) )。
步骤5：最终结果
- 结果存储在
dp[n][m]中，即整个字符串 s 和整个模式 p 是否匹配。
示例推演
以 s = "aab", p = "cab" 为例（只包含 '*' 量词，用于简单演示）：
- n=3, m=5。
- 初始化 dp[0][0]=true。
- 初始化 dp[0][j]：p="cab" 中 '' 可以匹配零个，所以 dp[0][2]=true（跳过 c），dp[0][4]=true（跳过 a*），最终 dp[0][5]=true。
- 填表过程（略过详细单元格计算），最终 dp[3][5]=true，匹配成功。
复杂度分析
- 时间复杂度：O(n × m)，其中 n 为 s 长度，m 为 p 长度。
- 空间复杂度：O(n × m)，可优化到 O(m) 但实现稍复杂。
关键点
- 处理量词时要考虑前面字符 prev，并且分情况讨论零个、一个、多个的匹配。
- 初始化空字符串匹配模式时，只有 '*' 和 '?' 能让模式匹配空串，'+' 不行。
- 状态转移时，注意下标不要越界（例如 j≥2 时才处理量词）。
通过以上步骤，我们可以判断字符串 s 是否与带有 '.'、'*'、'+'、'?' 的正则表达式模式 p 完全匹配。