 空间原地 DP 的五层解法深度解析)
LeetCode 10 正则表达式匹配从递归到 O(n) 空间原地 DP 的五层解法深度解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇以 leetcode 仓库中的题解文档 regular-expression-matching.md 为主体系统拆解 LeetCode 10「正则表达式匹配」问题给定字符串s与模式p其中.匹配任意单个字符、x*表示「x出现零次或多次」要求实现整串全匹配而非子串部分匹配。文章完整继承原文档的五种解法脉络——朴素递归、自顶向下记忆化、自底向上二维 DP、滚动数组空间优化、原地一维 DP 最优解并结合仓库中 python/0010-regular-expression-matching.py、cpp/0010-regular-expression-matching.cpp 等多语言实现交叉印证。读完后你将能够独立推导出该问题的状态定义与转移方程理解每一层优化的动机指数级重复子问题 → 记忆化 → 表格化 → 压缩维度 → 原地更新并掌握实现中所有易错边界。1. 问题语义与前置知识题目对模式字符的约定如下模式元素语义注意a-z匹配对应的小写字母本身—.匹配任意单个字符只匹配一个字符不能跨字符x*匹配前一个元素x出现零次或多次*不独立存在依附于前一个元素例如a*只匹配 0 个或多个a.*才匹配任意长度的任意字符序列匹配必须是完整的例如s aa、p a应返回false因为a没有匹配上整个字符串。仓库的 cpp/0010-regular-expression-matching.cpp 文件头注释同样明确了这一点Matching should cover the entire input string (not partial)。原文档给出的前置知识有三项递归把「s[i:]能否被p[j:]匹配」拆成更小的子问题并设计好基准情形动态规划记忆化 / 自顶向下对重叠子问题缓存结果消除重复计算动态规划表格化 / 自底向上用二维表自后向前填充避免递归开销。整个问题的核心状态定义在五种解法中保持一致dfs(i, j)/dp[i][j]表示字符串后缀s[i:]能否被模式后缀p[j:]完整匹配。所有解法的差异只在于如何求这个状态指数递归、带缓存递归、二维表、一维滚动、一维原地更新。2. 解法一朴素递归2.1 思路*带来两个分支在每一步我们根据模式当前字符p[j]是否为「带*的组合」分两种情况下一个模式字符不是*当前两个字符必须匹配s[i] p[j]或p[j] .然后双指针同时前进dfs(i 1, j 1)不匹配则返回false。下一个模式字符是*即p[j1] *对x*有两个选择——跳过把x*整体当零次出现直接dfs(i, j 2)使用若当前字符匹配match为真则用x*吃掉s的一个字符模式位置保持不动以便继续匹配更多即dfs(i 1, j)。基准情形j n模式耗尽时仅当i m字符串也耗尽才返回true。2.2 算法步骤令m len(s)、n len(p)定义dfs(i, j)i、j分别为s、p的当前下标j到达模式末尾返回i m计算match (i m) and (s[i] p[j] or p[j] .)若j 1 n且p[j 1] *返回dfs(i, j 2) or (match and dfs(i 1, j))否则match为真则返回dfs(i 1, j 1)否则返回false入口为dfs(0, 0)。2.3 参考实现Python / Javaclass Solution: def isMatch(self, s: str, p: str) - bool: m, n len(s), len(p) def dfs(i, j): if j n: return i m match i m and (s[i] p[j] or p[j] .) if (j 1) n and p[j 1] *: return (dfs(i, j 2) or # dont use * (match and dfs(i 1, j))) # use * if match: return dfs(i 1, j 1) return False return dfs(0, 0)public class Solution { public boolean isMatch(String s, String p) { int m s.length(), n p.length(); return dfs(0, 0, s, p, m, n); } private boolean dfs(int i, int j, String s, String p, int m, int n) { if (j n) return i m; boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 n p.charAt(j 1) *) { return dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } if (match) { return dfs(i 1, j 1, s, p, m, n); } return false; } }原文档还给出了 C、JavaScript、C#、Go、Kotlin、Swift、Rust 八种语言的等价实现逻辑完全一致。2.4 复杂度为什么朴素递归不可取时间复杂度O(2^(m n))。每个x*都可能产生「用/不用」的二叉分支且不同路径会反复计算相同的(i, j)状态。仓库 javascript/0010-regular-expression-matching.js 中对暴力 DFS 的标注是O((N M) * 2^(N M/2))因*必须成对出现可产生分支的模式位置约为M/2量级结论与原文档一致。空间复杂度O(m n)即递归栈深度。这正是引入记忆化的动机状态空间本身只有 (m1) × (n1) 个但朴素递归的调用树呈指数展开。3. 解法二自顶向下记忆化Top-Down DP3.1 思路缓存(i, j)状态递归的指数复杂度全部来自重叠子问题dfs(i, j)的状态总数只有 O(m × n)把每次计算结果存进缓存后续相同状态直接查表返回即可。实现上缓存有两种等价形式哈希表Python 的dict、C 的mappairint,int, bool二维数组用「未计算」哨兵值区分缓存命中与未命中Java 用Boolean[][]的nullC/Go/Rust 用-1C# 用bool?Swift 用Bool?。注意一个实现细节基准情形j n的结论i m本身不依赖缓存应在查缓存之前直接返回否则当i越界时缓存数组dp[i][j]的下标访问会越界。3.2 算法步骤令m len(s)、n len(p)创建缓存定义dfs(i, j)j n返回i m(i, j)已在缓存中直接返回缓存值计算match若p[j1] *缓存并返回dfs(i, j 2) or (match and dfs(i 1, j))否则match为真则缓存并返回dfs(i 1, j 1)否则缓存并返回false入口dfs(0, 0)。3.3 参考实现Python / Java / Cclass Solution: def isMatch(self, s: str, p: str) - bool: m, n len(s), len(p) cache {} def dfs(i, j): if j n: return i m if (i, j) in cache: return cache[(i, j)] match i m and (s[i] p[j] or p[j] .) if (j 1) n and p[j 1] *: cache[(i, j)] (dfs(i, j 2) or (match and dfs(i 1, j))) return cache[(i, j)] if match: cache[(i, j)] dfs(i 1, j 1) return cache[(i, j)] cache[(i, j)] False return False return dfs(0, 0)public class Solution { private Boolean[][] dp; public boolean isMatch(String s, String p) { int m s.length(), n p.length(); dp new Boolean[m 1][n 1]; return dfs(0, 0, s, p, m, n); } private boolean dfs(int i, int j, String s, String p, int m, int n) { if (j n) { return i m; } if (dp[i][j] ! null) { return dp[i][j]; } boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 n p.charAt(j 1) *) { dp[i][j] dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } else { dp[i][j] match dfs(i 1, j 1, s, p, m, n); } return dp[i][j]; } }class Solution { vectorvectorint dp; public: bool isMatch(string s, string p) { int m s.length(), n p.length(); dp.assign(m 1, vectorint(n 1, -1)); return dfs(0, 0, s, p, m, n); } private: bool dfs(int i, int j, string s, string p, int m, int n) { if (j n) { return i m; } if (dp[i][j] ! -1) { return dp[i][j]; } bool match i m (s[i] p[j] || p[j] .); if (j 1 n p[j 1] *) { dp[i][j] dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } else { dp[i][j] match dfs(i 1, j 1, s, p, m, n); } return dp[i][j]; } };3.4 仓库印证与复杂度仓库 python/0010-regular-expression-matching.py 中给出了TOP DOWN MEMOIZATION版本其基准情形写法略有不同先判(i, j)是否已缓存再判断i len(s) and j len(p)返回True、j len(p)返回False——与文档版「先判j n」在语义上等价只是把「双指针同时越界」的终止条件写得更显式。java/0010-regular-expression-matching.java 与 cpp/0010-regular-expression-matching.cpp 也是同一思路Java 用boolean[][]配合「false表示未算」的隐式哨兵C 用mappairint,int, bool。时间复杂度O(m × n)——每个状态只计算一次每次转移 O(1)空间复杂度O(m × n)——缓存最多存 (m1) × (n1) 个状态外加 O(m n) 递归栈。4. 解法三自底向上表格化Bottom-Up DP4.1 思路从字符串尾部倒着填表既然状态dp[i][j]s[i:]能否匹配p[j:]只依赖dp[i][j2]、dp[i1][j]、dp[i1][j1]这三个「更靠右下」的状态那么从两串末尾向开头遍历即可保证依赖先行。这消除了递归栈开销也让「空模式只能匹配空串」的边界自然融入表格。关键点表大小为(m1) × (n1)多出来的最后一行/列专门表示「字符串/模式剩余为空」的情况唯一的初始值dp[m][n] true两个空串互相匹配转移方程与递归版一一对应match (i m) and (s[i] p[j] or p[j] .) 若 j1 n 且 p[j1] *: dp[i][j] dp[i][j2] # 零次出现跳过 x* 若 match: dp[i][j] dp[i1][j] or dp[i][j] # 至少一次吃掉一个字符 否则: 若 match: dp[i][j] dp[i1][j1] # 普通字符双指针前进最终答案在dp[0][0]。4.2 算法步骤建(m1) × (n1)布尔表dp全置false置基准dp[m][n] truei从m递减到0j从n-1递减到0每格先算match再按「是否x*」选择上面的转移返回dp[0][0]。4.3 参考实现Python / Java / Cclass Solution: def isMatch(self, s: str, p: str) - bool: dp [[False] * (len(p) 1) for i in range(len(s) 1)] dp[len(s)][len(p)] True for i in range(len(s), -1, -1): for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) if (j 1) len(p) and p[j 1] *: dp[i][j] dp[i][j 2] if match: dp[i][j] dp[i 1][j] or dp[i][j] elif match: dp[i][j] dp[i 1][j 1] return dp[0][0]class Solution { public boolean isMatch(String s, String p) { int m s.length(), n p.length(); boolean[][] dp new boolean[m 1][n 1]; dp[m][n] true; for (int i m; i 0; i--) { for (int j n - 1; j 0; j--) { boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if ((j 1) n p.charAt(j 1) *) { dp[i][j] dp[i][j 2]; if (match) { dp[i][j] dp[i 1][j] || dp[i][j]; } } else if (match) { dp[i][j] dp[i 1][j 1]; } } } return dp[0][0]; } }class Solution { public: bool isMatch(string s, string p) { int m s.length(), n p.length(); vectorvectorbool dp(m 1, vectorbool(n 1, false)); dp[m][n] true; for (int i m; i 0; i--) { for (int j n - 1; j 0; j--) { bool match i m (s[i] p[j] || p[j] .); if ((j 1) n p[j 1] *) { dp[i][j] dp[i][j 2]; if (match) { dp[i][j] dp[i 1][j] || dp[i][j]; } } else if (match) { dp[i][j] dp[i 1][j 1]; } } } return dp[0][0]; } };仓库的 python/0010-regular-expression-matching.py 顶部BOTTOM-UP Dynamic Programming段落、javascript/0010-regular-expression-matching.js 中基于tabu表的自底向上版本与上述实现逐行同构可以互相印证转移方程的正确性。4.4 手推示例s aap a*按上述规则填表行索引i对应s[i:]列索引j对应p[j:]模式末列即p[2:] dp[i][j]a*j0*j1j2s[0:]aai0truefalsefalses[1:]ai1truefalsefalses[2:]i2truefalsetrue填表过程倒序dp[2][2] true基准末行i2dp[2][1]无意义的孤立*保持falsedp[2][0]是x*分支dp[2][0] dp[2][2] true空串可被a*零次匹配j2列其余为false非空串匹配空模式不成立dp[1][0]matchs[1]a p[0]a为真dp[1][0] dp[2][0] or dp[1][2] truedp[0][0]同理dp[0][0] dp[1][0] or dp[0][2] true。答案为truea*吃掉两个a。注意x*分支里dp[i1][j]这一支正是「用一次*后模式指针不动、继续尝试吃掉更多字符」在表格中的体现。4.5 复杂度时间复杂度O(m × n)空间复杂度O(m × n)——整张表都要保留。5. 解法四滚动数组空间优化O(n) 空间5.1 思路每行只依赖下一行与当前行观察 4.4 的转移计算第i行时用到的外部依赖只有dp[i1][j]下一行同列和行内已算好的dp[i][j2]、dp[i1][j1]后者在二维表里是dp[i1][j1]。因此不需要保存整张二维表压缩为两个一维数组dp→ 代表第i1行nextDp→ 正在构造的第i行。每处理完一行dp nextDp即可。一个容易忽略的边界二维表里第i行末元素dp[i][n]的语义是「s[i:]匹配空模式」它只在i m时为true。压缩后这一列不会从「下一行」自然继承必须在每行开头显式重置nextDp[n] (i m)。漏掉这步是滚动数组版最常见的 bug。5.2 算法步骤建一维布尔数组dp长度n 1置dp[n] true对应第m行的基准i从m递减到0新建nextDp并置nextDp[n] (i m)j从n-1递减到0算matchx*分支nextDp[j] nextDp[j2]若match再nextDp[j] | dp[j]普通分支若matchnextDp[j] dp[j1]行末dp nextDp返回dp[0]。5.3 参考实现Python / Java / Goclass Solution: def isMatch(self, s: str, p: str) - bool: dp [False] * (len(p) 1) dp[len(p)] True for i in range(len(s), -1, -1): nextDp [False] * (len(p) 1) nextDp[len(p)] (i len(s)) for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) if (j 1) len(p) and p[j 1] *: nextDp[j] nextDp[j 2] if match: nextDp[j] | dp[j] elif match: nextDp[j] dp[j 1] dp nextDp return dp[0]public class Solution { public boolean isMatch(String s, String p) { boolean[] dp new boolean[p.length() 1]; dp[p.length()] true; for (int i s.length(); i 0; i--) { boolean[] nextDp new boolean[p.length() 1]; nextDp[p.length()] (i s.length()); for (int j p.length() - 1; j 0; j--) { boolean match i s.length() (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 p.length() p.charAt(j 1) *) { nextDp[j] nextDp[j 2]; if (match) { nextDp[j] | dp[j]; } } else if (match) { nextDp[j] dp[j 1]; } } dp nextDp; } return dp[0]; } }func isMatch(s, p string) bool { m, n : len(s), len(p) dp : make([]bool, n1) dp[n] true for i : m; i 0; i-- { nextDp : make([]bool, n1) nextDp[n] i m for j : n - 1; j 0; j-- { match : i m (s[i] p[j] || p[j] .) if j1 n p[j1] * { nextDp[j] nextDp[j2] || (match dp[j]) } else if match { nextDp[j] dp[j1] } } dp nextDp } return dp[0] }5.4 复杂度时间复杂度O(m × n)空间复杂度O(n)——两个长度为n1的数组。6. 解法五原地一维 DP最优空间实现6.1 思路连第二个数组都不要——关键是保护对角线滚动数组版之所以需要nextDp是因为原地更新会覆盖尚未使用的旧值。逐项检查转移依赖在原地更新时的命运j从右往左更新dp[j 2]跳过x*位于j右侧、本行已经算完可用dp[j]旧值即dp[i1][j]x*至少一次分支本位置还没被覆盖可用dp[j 1]的旧值即dp[i1][j1]普通字符分支的对角线依赖在j向右移动到j1时已被覆盖丢失解决办法是引入一个标量dp1充当「对角线追踪器」每覆盖一个位置前先把该位置的旧值存入dp1供左侧下一个j用作对角线。具体节奏是每轮外层循环开始dp1 dp[n]保存行尾旧值它将是j n-1处的对角线然后重置dp[n] (i m)j从n-1到0先按转移方程算出res此时dp[j]、dp[j2]、dp1恰好分别是dp[i1][j]、当前行dp[i][j2]、对角线dp[i1][j1]再执行dp1 dp[j]; dp[j] res旧值先传给对角线追踪器再写入新值。6.2 算法步骤建dp长度n1dp[n] truei从m到0dp1 dp[n]dp[n] (i m)j从n-1到0算match与res交换dp[j], dp1返回dp[0]。6.3 参考实现Python / Java / Rustclass Solution: def isMatch(self, s: str, p: str) - bool: dp [False] * (len(p) 1) dp[len(p)] True for i in range(len(s), -1, -1): dp1 dp[len(p)] dp[len(p)] (i len(s)) for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) res False if (j 1) len(p) and p[j 1] *: res dp[j 2] if match: res | dp[j] elif match: res dp1 dp[j], dp1 res, dp[j] return dp[0]public class Solution { public boolean isMatch(String s, String p) { boolean[] dp new boolean[p.length() 1]; dp[p.length()] true; for (int i s.length(); i 0; i--) { boolean dp1 dp[p.length()]; dp[p.length()] (i s.length()); for (int j p.length() - 1; j 0; j--) { boolean match i s.length() (s.charAt(i) p.charAt(j) || p.charAt(j) .); boolean res false; if (j 1 p.length() p.charAt(j 1) *) { res dp[j 2]; if (match) { res | dp[j]; } } else if (match) { res dp1; } dp1 dp[j]; dp[j] res; } } return dp[0]; } }impl Solution { pub fn is_match(s: String, p: String) - bool { let s s.as_bytes(); let p p.as_bytes(); let (m, n) (s.len(), p.len()); let mut dp vec![false; n 1]; dp[n] true; for i in (0..m).rev() { let mut dp1 dp[n]; dp[n] i m; for j in (0..n).rev() { let matched i m (s[i] p[j] || p[j] b.); let mut res false; if j 1 n p[j 1] b* { res dp[j 2]; if matched { res res || dp[j]; } } else if matched { res dp1; } dp1 dp[j]; dp[j] res; } } dp[0] } }注意 Python 版利用元组解包dp[j], dp1 res, dp[j]一行完成「旧值转移 新值写入」Go 版同理dp[j], dp1 res, dp[j]而 Java/C/Rust 需要两条显式语句顺序不能颠倒必须先dp1 dp[j]再dp[j] res。6.4 复杂度时间复杂度O(m × n)空间复杂度O(n)——单个一维数组加一个标量且无需每轮重新分配nextDp常数上优于滚动数组版。7. 五种解法横向对比解法时间复杂度空间复杂度核心手段适用场景朴素递归O(2^(m n))O(m n) 递归栈直接搜索「用/不用*」理解状态拆分不可通过数据记忆化自顶向下O(m × n)O(m × n)缓存(i, j)状态首选实现代码最接近思路表格化自底向上O(m × n)O(m × n)倒序填二维表面试白板推导、可视化状态表滚动数组O(m × n)O(n)双一维数组逐行滚动需要压缩空间且追求清晰原地一维 DPO(m × n)O(n)单数组 对角线标量dp1空间敏感、竞赛优化其中m为s长度、n为p长度。从源码结构看仓库 python/0010-regular-expression-matching.py 同时保留了「自底向上表格 自顶向下记忆化」两个版本javascript/0010-regular-expression-matching.js 则把「暴力 DFS → 矩阵记忆化 → 自底向上 tabulation」三个阶段串在同一文件里与本文的递进脉络完全吻合。8. 常见陷阱Common Pitfalls原文档总结了五类高频错误结合上文解法逐条说明误解*的语义*表示「前一个元素的零次或多次」而不是「任意字符的零次或多次」。把a*当成通配任意序列是典型错误真正匹配任意序列的写法是.*。忘记x*可以匹配零次遇到x*若只考虑「至少吃一个字符」的分支会漏掉整段跳过的情形。两个分支必须都探索dfs(i, j2)跳过与match and dfs(i1, j)吃掉一个。检查*时的 off-by-one 错误判断x*组合要看的是p[j1]而不是p[j]且访问前必须先确认j 1 n否则越界。各语言实现中这一行都是硬性前置条件如 Python 的(j 1) n and p[j 1] *。空串/空模式边界模式耗尽j n时仅当字符串也耗尽才匹配成功而字符串先耗尽但模式未耗尽时仍可能成功——只要剩余模式全部是x*组合例如a*b*c*可匹配空串。这就是自底向上填表时末行dp[m][j]不能全置false、而要靠x*分支从dp[m][n] true向右传播的原因。DP 转移方向写反状态依赖dp[i1][j]、dp[i][j2]、dp[i1][j1]必须从两串末尾向开头遍历。若正向遍历引用到的状态尚未计算对原地一维版j必须从右往左否则对角线值会被提前覆盖这正是需要dp1的根本原因。9. 小结与延伸阅读本文以 articles/regular-expression-matching.md 为骨架完整呈现了 LeetCode 10 从「指数级二分支递归」到「O(n) 空间原地一维 DP」的完整推导链统一的状态定义dp[i][j] s[i:] 能否匹配 p[j:]贯穿始终五种解法只是对「如何求值该状态」的逐步工程化。掌握这条主线后可以平移到仓库中语义相近的 python/0044-wildcard-matching.py通配符匹配?/*的转移结构与本文几乎同构只是*不依附于前一字符。仓库内其他语言的 0010 题解C、Java、JavaScript 等均可作为同一算法跨语言写法的对照练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 10 正则表达式匹配：从递归到 O(n) 空间原地 DP 的五层解法深度解析
LeetCode 10 正则表达式匹配从递归到 O(n) 空间原地 DP 的五层解法深度解析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇以 leetcode 仓库中的题解文档 regular-expression-matching.md 为主体系统拆解 LeetCode 10「正则表达式匹配」问题给定字符串s与模式p其中.匹配任意单个字符、x*表示「x出现零次或多次」要求实现整串全匹配而非子串部分匹配。文章完整继承原文档的五种解法脉络——朴素递归、自顶向下记忆化、自底向上二维 DP、滚动数组空间优化、原地一维 DP 最优解并结合仓库中 python/0010-regular-expression-matching.py、cpp/0010-regular-expression-matching.cpp 等多语言实现交叉印证。读完后你将能够独立推导出该问题的状态定义与转移方程理解每一层优化的动机指数级重复子问题 → 记忆化 → 表格化 → 压缩维度 → 原地更新并掌握实现中所有易错边界。1. 问题语义与前置知识题目对模式字符的约定如下模式元素语义注意a-z匹配对应的小写字母本身—.匹配任意单个字符只匹配一个字符不能跨字符x*匹配前一个元素x出现零次或多次*不独立存在依附于前一个元素例如a*只匹配 0 个或多个a.*才匹配任意长度的任意字符序列匹配必须是完整的例如s aa、p a应返回false因为a没有匹配上整个字符串。仓库的 cpp/0010-regular-expression-matching.cpp 文件头注释同样明确了这一点Matching should cover the entire input string (not partial)。原文档给出的前置知识有三项递归把「s[i:]能否被p[j:]匹配」拆成更小的子问题并设计好基准情形动态规划记忆化 / 自顶向下对重叠子问题缓存结果消除重复计算动态规划表格化 / 自底向上用二维表自后向前填充避免递归开销。整个问题的核心状态定义在五种解法中保持一致dfs(i, j)/dp[i][j]表示字符串后缀s[i:]能否被模式后缀p[j:]完整匹配。所有解法的差异只在于如何求这个状态指数递归、带缓存递归、二维表、一维滚动、一维原地更新。2. 解法一朴素递归2.1 思路*带来两个分支在每一步我们根据模式当前字符p[j]是否为「带*的组合」分两种情况下一个模式字符不是*当前两个字符必须匹配s[i] p[j]或p[j] .然后双指针同时前进dfs(i 1, j 1)不匹配则返回false。下一个模式字符是*即p[j1] *对x*有两个选择——跳过把x*整体当零次出现直接dfs(i, j 2)使用若当前字符匹配match为真则用x*吃掉s的一个字符模式位置保持不动以便继续匹配更多即dfs(i 1, j)。基准情形j n模式耗尽时仅当i m字符串也耗尽才返回true。2.2 算法步骤令m len(s)、n len(p)定义dfs(i, j)i、j分别为s、p的当前下标j到达模式末尾返回i m计算match (i m) and (s[i] p[j] or p[j] .)若j 1 n且p[j 1] *返回dfs(i, j 2) or (match and dfs(i 1, j))否则match为真则返回dfs(i 1, j 1)否则返回false入口为dfs(0, 0)。2.3 参考实现Python / Javaclass Solution: def isMatch(self, s: str, p: str) - bool: m, n len(s), len(p) def dfs(i, j): if j n: return i m match i m and (s[i] p[j] or p[j] .) if (j 1) n and p[j 1] *: return (dfs(i, j 2) or # dont use * (match and dfs(i 1, j))) # use * if match: return dfs(i 1, j 1) return False return dfs(0, 0)public class Solution { public boolean isMatch(String s, String p) { int m s.length(), n p.length(); return dfs(0, 0, s, p, m, n); } private boolean dfs(int i, int j, String s, String p, int m, int n) { if (j n) return i m; boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 n p.charAt(j 1) *) { return dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } if (match) { return dfs(i 1, j 1, s, p, m, n); } return false; } }原文档还给出了 C、JavaScript、C#、Go、Kotlin、Swift、Rust 八种语言的等价实现逻辑完全一致。2.4 复杂度为什么朴素递归不可取时间复杂度O(2^(m n))。每个x*都可能产生「用/不用」的二叉分支且不同路径会反复计算相同的(i, j)状态。仓库 javascript/0010-regular-expression-matching.js 中对暴力 DFS 的标注是O((N M) * 2^(N M/2))因*必须成对出现可产生分支的模式位置约为M/2量级结论与原文档一致。空间复杂度O(m n)即递归栈深度。这正是引入记忆化的动机状态空间本身只有 (m1) × (n1) 个但朴素递归的调用树呈指数展开。3. 解法二自顶向下记忆化Top-Down DP3.1 思路缓存(i, j)状态递归的指数复杂度全部来自重叠子问题dfs(i, j)的状态总数只有 O(m × n)把每次计算结果存进缓存后续相同状态直接查表返回即可。实现上缓存有两种等价形式哈希表Python 的dict、C 的mappairint,int, bool二维数组用「未计算」哨兵值区分缓存命中与未命中Java 用Boolean[][]的nullC/Go/Rust 用-1C# 用bool?Swift 用Bool?。注意一个实现细节基准情形j n的结论i m本身不依赖缓存应在查缓存之前直接返回否则当i越界时缓存数组dp[i][j]的下标访问会越界。3.2 算法步骤令m len(s)、n len(p)创建缓存定义dfs(i, j)j n返回i m(i, j)已在缓存中直接返回缓存值计算match若p[j1] *缓存并返回dfs(i, j 2) or (match and dfs(i 1, j))否则match为真则缓存并返回dfs(i 1, j 1)否则缓存并返回false入口dfs(0, 0)。3.3 参考实现Python / Java / Cclass Solution: def isMatch(self, s: str, p: str) - bool: m, n len(s), len(p) cache {} def dfs(i, j): if j n: return i m if (i, j) in cache: return cache[(i, j)] match i m and (s[i] p[j] or p[j] .) if (j 1) n and p[j 1] *: cache[(i, j)] (dfs(i, j 2) or (match and dfs(i 1, j))) return cache[(i, j)] if match: cache[(i, j)] dfs(i 1, j 1) return cache[(i, j)] cache[(i, j)] False return False return dfs(0, 0)public class Solution { private Boolean[][] dp; public boolean isMatch(String s, String p) { int m s.length(), n p.length(); dp new Boolean[m 1][n 1]; return dfs(0, 0, s, p, m, n); } private boolean dfs(int i, int j, String s, String p, int m, int n) { if (j n) { return i m; } if (dp[i][j] ! null) { return dp[i][j]; } boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 n p.charAt(j 1) *) { dp[i][j] dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } else { dp[i][j] match dfs(i 1, j 1, s, p, m, n); } return dp[i][j]; } }class Solution { vectorvectorint dp; public: bool isMatch(string s, string p) { int m s.length(), n p.length(); dp.assign(m 1, vectorint(n 1, -1)); return dfs(0, 0, s, p, m, n); } private: bool dfs(int i, int j, string s, string p, int m, int n) { if (j n) { return i m; } if (dp[i][j] ! -1) { return dp[i][j]; } bool match i m (s[i] p[j] || p[j] .); if (j 1 n p[j 1] *) { dp[i][j] dfs(i, j 2, s, p, m, n) || (match dfs(i 1, j, s, p, m, n)); } else { dp[i][j] match dfs(i 1, j 1, s, p, m, n); } return dp[i][j]; } };3.4 仓库印证与复杂度仓库 python/0010-regular-expression-matching.py 中给出了TOP DOWN MEMOIZATION版本其基准情形写法略有不同先判(i, j)是否已缓存再判断i len(s) and j len(p)返回True、j len(p)返回False——与文档版「先判j n」在语义上等价只是把「双指针同时越界」的终止条件写得更显式。java/0010-regular-expression-matching.java 与 cpp/0010-regular-expression-matching.cpp 也是同一思路Java 用boolean[][]配合「false表示未算」的隐式哨兵C 用mappairint,int, bool。时间复杂度O(m × n)——每个状态只计算一次每次转移 O(1)空间复杂度O(m × n)——缓存最多存 (m1) × (n1) 个状态外加 O(m n) 递归栈。4. 解法三自底向上表格化Bottom-Up DP4.1 思路从字符串尾部倒着填表既然状态dp[i][j]s[i:]能否匹配p[j:]只依赖dp[i][j2]、dp[i1][j]、dp[i1][j1]这三个「更靠右下」的状态那么从两串末尾向开头遍历即可保证依赖先行。这消除了递归栈开销也让「空模式只能匹配空串」的边界自然融入表格。关键点表大小为(m1) × (n1)多出来的最后一行/列专门表示「字符串/模式剩余为空」的情况唯一的初始值dp[m][n] true两个空串互相匹配转移方程与递归版一一对应match (i m) and (s[i] p[j] or p[j] .) 若 j1 n 且 p[j1] *: dp[i][j] dp[i][j2] # 零次出现跳过 x* 若 match: dp[i][j] dp[i1][j] or dp[i][j] # 至少一次吃掉一个字符 否则: 若 match: dp[i][j] dp[i1][j1] # 普通字符双指针前进最终答案在dp[0][0]。4.2 算法步骤建(m1) × (n1)布尔表dp全置false置基准dp[m][n] truei从m递减到0j从n-1递减到0每格先算match再按「是否x*」选择上面的转移返回dp[0][0]。4.3 参考实现Python / Java / Cclass Solution: def isMatch(self, s: str, p: str) - bool: dp [[False] * (len(p) 1) for i in range(len(s) 1)] dp[len(s)][len(p)] True for i in range(len(s), -1, -1): for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) if (j 1) len(p) and p[j 1] *: dp[i][j] dp[i][j 2] if match: dp[i][j] dp[i 1][j] or dp[i][j] elif match: dp[i][j] dp[i 1][j 1] return dp[0][0]class Solution { public boolean isMatch(String s, String p) { int m s.length(), n p.length(); boolean[][] dp new boolean[m 1][n 1]; dp[m][n] true; for (int i m; i 0; i--) { for (int j n - 1; j 0; j--) { boolean match i m (s.charAt(i) p.charAt(j) || p.charAt(j) .); if ((j 1) n p.charAt(j 1) *) { dp[i][j] dp[i][j 2]; if (match) { dp[i][j] dp[i 1][j] || dp[i][j]; } } else if (match) { dp[i][j] dp[i 1][j 1]; } } } return dp[0][0]; } }class Solution { public: bool isMatch(string s, string p) { int m s.length(), n p.length(); vectorvectorbool dp(m 1, vectorbool(n 1, false)); dp[m][n] true; for (int i m; i 0; i--) { for (int j n - 1; j 0; j--) { bool match i m (s[i] p[j] || p[j] .); if ((j 1) n p[j 1] *) { dp[i][j] dp[i][j 2]; if (match) { dp[i][j] dp[i 1][j] || dp[i][j]; } } else if (match) { dp[i][j] dp[i 1][j 1]; } } } return dp[0][0]; } };仓库的 python/0010-regular-expression-matching.py 顶部BOTTOM-UP Dynamic Programming段落、javascript/0010-regular-expression-matching.js 中基于tabu表的自底向上版本与上述实现逐行同构可以互相印证转移方程的正确性。4.4 手推示例s aap a*按上述规则填表行索引i对应s[i:]列索引j对应p[j:]模式末列即p[2:] dp[i][j]a*j0*j1j2s[0:]aai0truefalsefalses[1:]ai1truefalsefalses[2:]i2truefalsetrue填表过程倒序dp[2][2] true基准末行i2dp[2][1]无意义的孤立*保持falsedp[2][0]是x*分支dp[2][0] dp[2][2] true空串可被a*零次匹配j2列其余为false非空串匹配空模式不成立dp[1][0]matchs[1]a p[0]a为真dp[1][0] dp[2][0] or dp[1][2] truedp[0][0]同理dp[0][0] dp[1][0] or dp[0][2] true。答案为truea*吃掉两个a。注意x*分支里dp[i1][j]这一支正是「用一次*后模式指针不动、继续尝试吃掉更多字符」在表格中的体现。4.5 复杂度时间复杂度O(m × n)空间复杂度O(m × n)——整张表都要保留。5. 解法四滚动数组空间优化O(n) 空间5.1 思路每行只依赖下一行与当前行观察 4.4 的转移计算第i行时用到的外部依赖只有dp[i1][j]下一行同列和行内已算好的dp[i][j2]、dp[i1][j1]后者在二维表里是dp[i1][j1]。因此不需要保存整张二维表压缩为两个一维数组dp→ 代表第i1行nextDp→ 正在构造的第i行。每处理完一行dp nextDp即可。一个容易忽略的边界二维表里第i行末元素dp[i][n]的语义是「s[i:]匹配空模式」它只在i m时为true。压缩后这一列不会从「下一行」自然继承必须在每行开头显式重置nextDp[n] (i m)。漏掉这步是滚动数组版最常见的 bug。5.2 算法步骤建一维布尔数组dp长度n 1置dp[n] true对应第m行的基准i从m递减到0新建nextDp并置nextDp[n] (i m)j从n-1递减到0算matchx*分支nextDp[j] nextDp[j2]若match再nextDp[j] | dp[j]普通分支若matchnextDp[j] dp[j1]行末dp nextDp返回dp[0]。5.3 参考实现Python / Java / Goclass Solution: def isMatch(self, s: str, p: str) - bool: dp [False] * (len(p) 1) dp[len(p)] True for i in range(len(s), -1, -1): nextDp [False] * (len(p) 1) nextDp[len(p)] (i len(s)) for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) if (j 1) len(p) and p[j 1] *: nextDp[j] nextDp[j 2] if match: nextDp[j] | dp[j] elif match: nextDp[j] dp[j 1] dp nextDp return dp[0]public class Solution { public boolean isMatch(String s, String p) { boolean[] dp new boolean[p.length() 1]; dp[p.length()] true; for (int i s.length(); i 0; i--) { boolean[] nextDp new boolean[p.length() 1]; nextDp[p.length()] (i s.length()); for (int j p.length() - 1; j 0; j--) { boolean match i s.length() (s.charAt(i) p.charAt(j) || p.charAt(j) .); if (j 1 p.length() p.charAt(j 1) *) { nextDp[j] nextDp[j 2]; if (match) { nextDp[j] | dp[j]; } } else if (match) { nextDp[j] dp[j 1]; } } dp nextDp; } return dp[0]; } }func isMatch(s, p string) bool { m, n : len(s), len(p) dp : make([]bool, n1) dp[n] true for i : m; i 0; i-- { nextDp : make([]bool, n1) nextDp[n] i m for j : n - 1; j 0; j-- { match : i m (s[i] p[j] || p[j] .) if j1 n p[j1] * { nextDp[j] nextDp[j2] || (match dp[j]) } else if match { nextDp[j] dp[j1] } } dp nextDp } return dp[0] }5.4 复杂度时间复杂度O(m × n)空间复杂度O(n)——两个长度为n1的数组。6. 解法五原地一维 DP最优空间实现6.1 思路连第二个数组都不要——关键是保护对角线滚动数组版之所以需要nextDp是因为原地更新会覆盖尚未使用的旧值。逐项检查转移依赖在原地更新时的命运j从右往左更新dp[j 2]跳过x*位于j右侧、本行已经算完可用dp[j]旧值即dp[i1][j]x*至少一次分支本位置还没被覆盖可用dp[j 1]的旧值即dp[i1][j1]普通字符分支的对角线依赖在j向右移动到j1时已被覆盖丢失解决办法是引入一个标量dp1充当「对角线追踪器」每覆盖一个位置前先把该位置的旧值存入dp1供左侧下一个j用作对角线。具体节奏是每轮外层循环开始dp1 dp[n]保存行尾旧值它将是j n-1处的对角线然后重置dp[n] (i m)j从n-1到0先按转移方程算出res此时dp[j]、dp[j2]、dp1恰好分别是dp[i1][j]、当前行dp[i][j2]、对角线dp[i1][j1]再执行dp1 dp[j]; dp[j] res旧值先传给对角线追踪器再写入新值。6.2 算法步骤建dp长度n1dp[n] truei从m到0dp1 dp[n]dp[n] (i m)j从n-1到0算match与res交换dp[j], dp1返回dp[0]。6.3 参考实现Python / Java / Rustclass Solution: def isMatch(self, s: str, p: str) - bool: dp [False] * (len(p) 1) dp[len(p)] True for i in range(len(s), -1, -1): dp1 dp[len(p)] dp[len(p)] (i len(s)) for j in range(len(p) - 1, -1, -1): match i len(s) and (s[i] p[j] or p[j] .) res False if (j 1) len(p) and p[j 1] *: res dp[j 2] if match: res | dp[j] elif match: res dp1 dp[j], dp1 res, dp[j] return dp[0]public class Solution { public boolean isMatch(String s, String p) { boolean[] dp new boolean[p.length() 1]; dp[p.length()] true; for (int i s.length(); i 0; i--) { boolean dp1 dp[p.length()]; dp[p.length()] (i s.length()); for (int j p.length() - 1; j 0; j--) { boolean match i s.length() (s.charAt(i) p.charAt(j) || p.charAt(j) .); boolean res false; if (j 1 p.length() p.charAt(j 1) *) { res dp[j 2]; if (match) { res | dp[j]; } } else if (match) { res dp1; } dp1 dp[j]; dp[j] res; } } return dp[0]; } }impl Solution { pub fn is_match(s: String, p: String) - bool { let s s.as_bytes(); let p p.as_bytes(); let (m, n) (s.len(), p.len()); let mut dp vec![false; n 1]; dp[n] true; for i in (0..m).rev() { let mut dp1 dp[n]; dp[n] i m; for j in (0..n).rev() { let matched i m (s[i] p[j] || p[j] b.); let mut res false; if j 1 n p[j 1] b* { res dp[j 2]; if matched { res res || dp[j]; } } else if matched { res dp1; } dp1 dp[j]; dp[j] res; } } dp[0] } }注意 Python 版利用元组解包dp[j], dp1 res, dp[j]一行完成「旧值转移 新值写入」Go 版同理dp[j], dp1 res, dp[j]而 Java/C/Rust 需要两条显式语句顺序不能颠倒必须先dp1 dp[j]再dp[j] res。6.4 复杂度时间复杂度O(m × n)空间复杂度O(n)——单个一维数组加一个标量且无需每轮重新分配nextDp常数上优于滚动数组版。7. 五种解法横向对比解法时间复杂度空间复杂度核心手段适用场景朴素递归O(2^(m n))O(m n) 递归栈直接搜索「用/不用*」理解状态拆分不可通过数据记忆化自顶向下O(m × n)O(m × n)缓存(i, j)状态首选实现代码最接近思路表格化自底向上O(m × n)O(m × n)倒序填二维表面试白板推导、可视化状态表滚动数组O(m × n)O(n)双一维数组逐行滚动需要压缩空间且追求清晰原地一维 DPO(m × n)O(n)单数组 对角线标量dp1空间敏感、竞赛优化其中m为s长度、n为p长度。从源码结构看仓库 python/0010-regular-expression-matching.py 同时保留了「自底向上表格 自顶向下记忆化」两个版本javascript/0010-regular-expression-matching.js 则把「暴力 DFS → 矩阵记忆化 → 自底向上 tabulation」三个阶段串在同一文件里与本文的递进脉络完全吻合。8. 常见陷阱Common Pitfalls原文档总结了五类高频错误结合上文解法逐条说明误解*的语义*表示「前一个元素的零次或多次」而不是「任意字符的零次或多次」。把a*当成通配任意序列是典型错误真正匹配任意序列的写法是.*。忘记x*可以匹配零次遇到x*若只考虑「至少吃一个字符」的分支会漏掉整段跳过的情形。两个分支必须都探索dfs(i, j2)跳过与match and dfs(i1, j)吃掉一个。检查*时的 off-by-one 错误判断x*组合要看的是p[j1]而不是p[j]且访问前必须先确认j 1 n否则越界。各语言实现中这一行都是硬性前置条件如 Python 的(j 1) n and p[j 1] *。空串/空模式边界模式耗尽j n时仅当字符串也耗尽才匹配成功而字符串先耗尽但模式未耗尽时仍可能成功——只要剩余模式全部是x*组合例如a*b*c*可匹配空串。这就是自底向上填表时末行dp[m][j]不能全置false、而要靠x*分支从dp[m][n] true向右传播的原因。DP 转移方向写反状态依赖dp[i1][j]、dp[i][j2]、dp[i1][j1]必须从两串末尾向开头遍历。若正向遍历引用到的状态尚未计算对原地一维版j必须从右往左否则对角线值会被提前覆盖这正是需要dp1的根本原因。9. 小结与延伸阅读本文以 articles/regular-expression-matching.md 为骨架完整呈现了 LeetCode 10 从「指数级二分支递归」到「O(n) 空间原地一维 DP」的完整推导链统一的状态定义dp[i][j] s[i:] 能否匹配 p[j:]贯穿始终五种解法只是对「如何求值该状态」的逐步工程化。掌握这条主线后可以平移到仓库中语义相近的 python/0044-wildcard-matching.py通配符匹配?/*的转移结构与本文几乎同构只是*不依附于前一字符。仓库内其他语言的 0010 题解C、Java、JavaScript 等均可作为同一算法跨语言写法的对照练习。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考