企业官网建设流程全解析

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. 问题语义与前置知识

题目对模式字符的约定如下：

匹配必须是完整的：例如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]是否为「带*的组合」分两种情况：

1. 下一个模式字符不是*：当前两个字符必须匹配（s[i] == p[j]或p[j] == '.'），然后双指针同时前进dfs(i + 1, j + 1)；不匹配则返回false。
2. 下一个模式字符是*（即p[j+1] == '*'）：对x*有两个选择——
   • 跳过：把x*整体当零次出现，直接dfs(i, j + 2)；
   • 使用：若当前字符匹配（match为真），则用x*吃掉s的一个字符，模式位置保持不动以便继续匹配更多，即dfs(i + 1, j)。

基准情形：j == n（模式耗尽）时，仅当i == m（字符串也耗尽）才返回true。

2.2 算法步骤

1. 令m = len(s)、n = len(p)；
2. 定义dfs(i, j)，i、j分别为s、p的当前下标；
3. j到达模式末尾：返回i == m；
4. 计算match = (i < m) and (s[i] == p[j] or p[j] == '.')；
5. 若j + 1 < n且p[j + 1] == '*'：返回dfs(i, j + 2) or (match and dfs(i + 1, j))；
6. 否则：match为真则返回dfs(i + 1, j + 1)，否则返回false；
7. 入口为dfs(0, 0)。

2.3 参考实现（Python / Java）

class 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 # don't 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)，即递归栈深度。

这正是引入记忆化的动机：状态空间本身只有 (m+1) × (n+1) 个，但朴素递归的调用树呈指数展开。

3. 解法二：自顶向下记忆化（Top-Down DP）

3.1 思路：缓存(i, j)状态

递归的指数复杂度全部来自重叠子问题：dfs(i, j)的状态总数只有 O(m × n)，把每次计算结果存进缓存，后续相同状态直接查表返回即可。实现上缓存有两种等价形式：

• 哈希表（Python 的dict、C++ 的map<pair<int,int>, bool>）；
• 二维数组，用「未计算」哨兵值区分缓存命中与未命中：Java 用Boolean[][]的null，C++/Go/Rust 用-1，C# 用bool?，Swift 用Bool?。

注意一个实现细节：基准情形j == n的结论（i == m）本身不依赖缓存，应在查缓存之前直接返回，否则当i越界时缓存数组dp[i][j]的下标访问会越界。

3.2 算法步骤

1. 令m = len(s)、n = len(p)，创建缓存；
2. 定义dfs(i, j)；
3. j == n：返回i == m；
4. (i, j)已在缓存中：直接返回缓存值；
5. 计算match；
6. 若p[j+1] == '*'：缓存并返回dfs(i, j + 2) or (match and dfs(i + 1, j))；
7. 否则：match为真则缓存并返回dfs(i + 1, j + 1)，否则缓存并返回false；
8. 入口dfs(0, 0)。

3.3 参考实现（Python / Java / C++）

class 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 { vector<vector<int>> dp; public: bool isMatch(string s, string p) { int m = s.length(), n = p.length(); dp.assign(m + 1, vector<int>(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++ 用map<pair<int,int>, bool>）。

• 时间复杂度：O(m × n)——每个状态只计算一次，每次转移 O(1)；
• 空间复杂度：O(m × n)——缓存最多存 (m+1) × (n+1) 个状态，外加 O(m + n) 递归栈。

4. 解法三：自底向上表格化（Bottom-Up DP）

4.1 思路：从字符串尾部倒着填表

既然状态dp[i][j]（s[i:]能否匹配p[j:]）只依赖dp[i][j+2]、dp[i+1][j]、dp[i+1][j+1]这三个「更靠右下」的状态，那么从两串末尾向开头遍历即可保证依赖先行。这消除了递归栈开销，也让「空模式只能匹配空串」的边界自然融入表格。

关键点：

• 表大小为(m+1) × (n+1)，多出来的最后一行/列专门表示「字符串/模式剩余为空」的情况；
• 唯一的初始值：dp[m][n] = true（两个空串互相匹配）；
• 转移方程（与递归版一一对应）：

match = (i < m) and (s[i] == p[j] or p[j] == '.') 若 j+1 < n 且 p[j+1] == '*': dp[i][j] = dp[i][j+2] # 零次出现：跳过 x* 若 match: dp[i][j] = dp[i+1][j] or dp[i][j] # 至少一次：吃掉一个字符 否则: 若 match: dp[i][j] = dp[i+1][j+1] # 普通字符：双指针前进

• 最终答案在dp[0][0]。

4.2 算法步骤

1. 建(m+1) × (n+1)布尔表dp，全置false；
2. 置基准dp[m][n] = true；
3. i从m递减到0，j从n-1递减到0；
4. 每格先算match，再按「是否x*」选择上面的转移；
5. 返回dp[0][0]。

4.3 参考实现（Python / Java / C++）

class 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(); vector<vector<bool>> dp(m + 1, vector<bool>(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 = "aa"，p = "a*"

按上述规则填表（行索引i对应s[i:]，列索引j对应p[j:]，模式末列即p[2:] = ""）：

填表过程（倒序）：

• dp[2][2] = true（基准）；
• 末行i=2：dp[2][1]无意义的孤立*保持false；dp[2][0]是x*分支，dp[2][0] = dp[2][2] = true（空串可被a*零次匹配）；
• j=2列其余为false（非空串匹配空模式不成立）；
• dp[1][0]：match（s[1]='a' == p[0]='a'）为真，dp[1][0] = dp[2][0] or dp[1][2] = true；
• dp[0][0]：同理dp[0][0] = dp[1][0] or dp[0][2] = true。

答案为true：a*吃掉两个a。注意x*分支里dp[i+1][j]这一支正是「用一次*后模式指针不动、继续尝试吃掉更多字符」在表格中的体现。

4.5 复杂度

• 时间复杂度：O(m × n)；
• 空间复杂度：O(m × n)——整张表都要保留。

5. 解法四：滚动数组空间优化（O(n) 空间）

5.1 思路：每行只依赖下一行与当前行

观察 4.4 的转移：计算第i行时用到的外部依赖只有dp[i+1][j]（下一行同列）和行内已算好的dp[i][j+2]、dp[i+1][j+1]（后者在二维表里是dp[i+1][j+1]）。因此不需要保存整张二维表，压缩为两个一维数组：

• dp→ 代表第i+1行；
• nextDp→ 正在构造的第i行。

每处理完一行，dp = nextDp即可。

一个容易忽略的边界：二维表里第i行末元素dp[i][n]的语义是「s[i:]匹配空模式」，它只在i == m时为true。压缩后这一列不会从「下一行」自然继承，必须在每行开头显式重置：nextDp[n] = (i == m)。漏掉这步是滚动数组版最常见的 bug。

5.2 算法步骤

1. 建一维布尔数组dp，长度n + 1，置dp[n] = true（对应第m行的基准）；
2. i从m递减到0：
   • 新建nextDp并置nextDp[n] = (i == m)；
   • j从n-1递减到0：
     • 算match；
     • x*分支：nextDp[j] = nextDp[j+2]，若match再nextDp[j] |= dp[j]；
     • 普通分支：若match，nextDp[j] = dp[j+1]；
   • 行末dp = nextDp；
3. 返回dp[0]。

5.3 参考实现（Python / Java / Go）

class 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, n+1) dp[n] = true for i := m; i >= 0; i-- { nextDp := make([]bool, n+1) nextDp[n] = i == m for j := n - 1; j >= 0; j-- { match := i < m && (s[i] == p[j] || p[j] == '.') if j+1 < n && p[j+1] == '*' { nextDp[j] = nextDp[j+2] || (match && dp[j]) } else if match { nextDp[j] = dp[j+1] } } dp = nextDp } return dp[0] }

5.4 复杂度

• 时间复杂度：O(m × n)；
• 空间复杂度：O(n)——两个长度为n+1的数组。

6. 解法五：原地一维 DP（最优空间实现）

6.1 思路：连第二个数组都不要——关键是保护对角线

滚动数组版之所以需要nextDp，是因为原地更新会覆盖尚未使用的旧值。逐项检查转移依赖在原地更新时的命运（j从右往左更新）：

• dp[j + 2]（跳过x*）：位于j右侧、本行已经算完，可用；
• dp[j]（旧值，即dp[i+1][j]，x*至少一次分支）：本位置还没被覆盖，可用；
• dp[j + 1]的旧值（即dp[i+1][j+1]，普通字符分支的对角线依赖）：在j向右移动到j+1时已被覆盖，丢失！

解决办法是引入一个标量dp1充当「对角线追踪器」：每覆盖一个位置前，先把该位置的旧值存入dp1，供左侧下一个j用作对角线。具体节奏是：

1. 每轮外层循环开始：dp1 = dp[n]（保存行尾旧值，它将是j = n-1处的对角线），然后重置dp[n] = (i == m)；
2. j从n-1到0：
   • 先按转移方程算出res（此时dp[j]、dp[j+2]、dp1恰好分别是dp[i+1][j]、当前行dp[i][j+2]、对角线dp[i+1][j+1]）；
   • 再执行dp1 = dp[j]; dp[j] = res（旧值先传给对角线追踪器，再写入新值）。

6.2 算法步骤

1. 建dp长度n+1，dp[n] = true；
2. i从m到0：
   • dp1 = dp[n]；dp[n] = (i == m)；
   • j从n-1到0：算match与res，交换dp[j], dp1；
3. 返回dp[0]。

6.3 参考实现（Python / Java / Rust）

class 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. 五种解法横向对比

其中m为s长度、n为p长度。从源码结构看，仓库 python/0010-regular-expression-matching.py 同时保留了「自底向上表格 + 自顶向下记忆化」两个版本，javascript/0010-regular-expression-matching.js 则把「暴力 DFS → 矩阵记忆化 → 自底向上 tabulation」三个阶段串在同一文件里，与本文的递进脉络完全吻合。

8. 常见陷阱（Common Pitfalls）

原文档总结了五类高频错误，结合上文解法逐条说明：

1. 误解*的语义：*表示「前一个元素的零次或多次」，而不是「任意字符的零次或多次」。把a*当成通配任意序列是典型错误；真正匹配任意序列的写法是.*。
2. 忘记x*可以匹配零次：遇到x*若只考虑「至少吃一个字符」的分支，会漏掉整段跳过的情形。两个分支必须都探索：dfs(i, j+2)（跳过）与match and dfs(i+1, j)（吃掉一个）。
3. 检查*时的 off-by-one 错误：判断x*组合要看的是p[j+1]而不是p[j]，且访问前必须先确认j + 1 < n，否则越界。各语言实现中这一行都是硬性前置条件（如 Python 的(j + 1) < n and p[j + 1] == "*"）。
4. 空串/空模式边界：模式耗尽（j == n）时仅当字符串也耗尽才匹配成功；而字符串先耗尽但模式未耗尽时仍可能成功——只要剩余模式全部是x*组合（例如a*b*c*可匹配空串）。这就是自底向上填表时末行dp[m][j]不能全置false、而要靠x*分支从dp[m][n] = true向右传播的原因。
5. DP 转移方向写反：状态依赖dp[i+1][j]、dp[i][j+2]、dp[i+1][j+1]，必须从两串末尾向开头遍历。若正向遍历，引用到的状态尚未计算；对原地一维版，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