线性动态规划：正则表达式匹配 题目描述 给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。 '.' 匹配任意单个字符。 '*' 匹配零个或多个前面的那一个元素。 匹配应覆盖整个字符串 s ，而不是部分字符串。 例如： s = "aa", p = "a" → false （ p 未匹配整个 s ） s = "aa", p = "a*" → true （ * 匹配零个或多个 a ） s = "ab", p = ".*" → true （ .* 表示匹配任意字符零次或多次） 解题过程 1. 定义状态 设 dp[i][j] 表示 s 的前 i 个字符（即 s[0...i-1] ）与 p 的前 j 个字符（即 p[0...j-1] ）是否匹配。 i 和 j 分别表示 s 和 p 的字符数量，从 0 到 len(s) 和 len(p) 。 最终目标是求 dp[len(s)][len(p)] 。 2. 初始化 dp[0][0] = true ：空字符串与空模式匹配。 对于 j > 0 ， dp[0][j] 表示空字符串能否被 p 的前 j 个字符匹配。只有当 p 的某些部分形如 a*b*c* （即偶数位置为 * 且可匹配零次）时才可能为 true 。具体规则： 若 p[j-1] == '*' ，则 dp[0][j] = dp[0][j-2] （跳过 x* 部分）。 否则为 false 。 3. 状态转移方程 遍历 i 从 1 到 len(s) ， j 从 1 到 len(p) ： 情况1： p[j-1] 是普通字符或 '.' 若 s[i-1] == p[j-1] 或 p[j-1] == '.' ，则当前字符匹配，状态继承自前一部分： dp[i][j] = dp[i-1][j-1] 。 否则 dp[i][j] = false 。 情况2： p[j-1] == '*' 此时 * 必须与它前面的字符 p[j-2] 结合（记为 char* 组合）。 子情况2.1：匹配零次 忽略 char* 组合，即 dp[i][j] = dp[i][j-2] 。 子情况2.2：匹配一次或多次 前提： s[i-1] 与 p[j-2] 匹配（即 s[i-1] == p[j-2] 或 p[j-2] == '.' ）。 此时 s 的当前字符可由 char* 匹配，问题转化为 s 的前 i-1 个字符是否与 p 的前 j 个字符匹配（因为 * 可继续匹配前面的字符）： dp[i][j] = dp[i-1][j] 。 综合两种情况： dp[i][j] = dp[i][j-2] || (匹配当前字符 && dp[i-1][j]) 。 4. 示例推导 以 s = "aab" , p = "c*a*b" 为例（应返回 true ）： 初始化： dp[0][0] = true ； dp[0][1] = false （ p[0]='c' ）； dp[0][2] = dp[0][0]=true （跳过 c* ）； dp[0][3]=false ； dp[0][4]=dp[0][2]=true （跳过 a* ）； dp[0][5]=false 。 填表过程（简略）： i=1, j=1 ： p[0]='c' 不匹配 s[0]='a' ，且 p[1]!='*' ，故 false 。 i=1, j=2 ： p[1]='*' ，匹配零次时 dp[1][2] = dp[1][0]=false ；匹配一次时需 s[0] 匹配 c ，不成立，故 false 。 逐步计算至 i=3, j=5 ：最终 dp[3][5] = true 。 5. 复杂度分析 时间复杂度：O(mn)，其中 m 和 n 分别为 s 和 p 的长度。 空间复杂度：可优化至 O(n)（使用滚动数组）。 关键点 处理 * 时需考虑匹配零次或多次，并利用已计算的子问题结果。 初始化空字符串的匹配情况是易错点。