LeetCode 10困难二维 DP
正则表达式匹配 图解题解
这道题到底在问什么
支持 . 和 *，判断模式 p 是否能匹配整个字符串 s。
- s
- "aab"
- p
- "c*a*b"
- 输出
- true
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合二维 DP。
- 4基底：空串匹配空模式 dp[0][0]=true空串和空模式一定匹配 → dp[0][0]=true，整张表从这里出发。
- 5x* 可匹配空串：dp[0][2] 继承 dp[0][0]c* 可以匹配「0 个 c」→ 跳过 c*，dp[0][2] 继承 dp[0][0]=1；同理 a* 让 dp[0][4] 继承 dp[0][2]=1。
- 6普通字符(或 .)相等 → 继承左上 dp[i-1][j-1]s 的 'a' 与 p 的 'a' 相等(若 p 是 '.' 也算匹配)→ 这格继承左上 dp[0][2]=1。
- 7遇到 *，先试匹配 0 次 → 看左 2 列 dp[i][j-2]遇到 c*，先考虑「一个 c 都不要」→ 跳过 c* 这两位，看 dp[1][0]=0 → 这格为 0。
- 8* 匹配多次：前字符吃当前 → 看上一行 dp[i-1][j]a* 且 'a' 能吃掉 s 的 'a' → 复用「吃掉这个 a 之前」的结果 dp[0][4]=1 → 这格为 1。
- 9a* 继续吃一个 a：dp[2][4] 看 dp[1][4]a* 再吃 s 的第二个 a → dp[2][4] 看上一行 dp[1][4]=1 → 仍为 1。
- 10结尾 b 相等 → 继承左上 dp[2][4]s 的 'b' 与 p 的 'b' 相等 → dp[3][5] 继承左上 dp[2][4]=1。
- 11答案在右下角 dp[m][n]=true右下角 dp[3][5]=1 → "aab" 匹配 "c*a*b"，返回 true。
- 14把这句话记住，下次遇到同类题，就能更快选出方向。
- 19把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：把 * 当成匹配任意字符串
✓ 对：* 只修饰它前一个字符
a* 表示零个或多个 a
✗ 错：只按样例推代码
✓ 对：先写清状态含义和边界条件
样例太少，隐藏用例专打边界
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def isMatch(self, s, p):
m, n = len(s), len(p)
dp = [[False]*(n+1) for _ in range(m+1)]
dp[0][0] = True
for j in range(2, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-2]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] in {s[i-1], '.'}:
dp[i][j] = dp[i-1][j-1]
elif p[j-1] == '*':
dp[i][j] = dp[i][j-2]
if p[j-2] in {s[i-1], '.'}:
dp[i][j] = dp[i][j] or dp[i-1][j]
return dp[m][n]C++
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<char>> dp(m + 1, vector<char>(n + 1, 0));
dp[0][0] = 1;
for (int j = 2; j <= n; j++)
if (p[j-1] == '*') dp[0][j] = dp[0][j-2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (p[j-1] == s[i-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1];
else if (p[j-1] == '*') {
dp[i][j] = dp[i][j-2];
if (p[j-2] == s[i-1] || p[j-2] == '.') dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
return dp[m][n];
}
};Java
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[0][0] = true;
for (int j = 2; j <= n; j++)
if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j-1), sc = s.charAt(i-1);
if (pc == sc || pc == '.') dp[i][j] = dp[i-1][j-1];
else if (pc == '*') {
dp[i][j] = dp[i][j-2];
char pv = p.charAt(j-2);
if (pv == sc || pv == '.') dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
return dp[m][n];
}
}套路模板 · 二维 DP
# 二维 DP 通用检查表
# 1. 定义状态/指针/容器
# 2. 每轮只做一个清晰动作
# 3. 更新答案并处理边界class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size(), n = p.size();
vector<vector<char>> dp(m + 1, vector<char>(n + 1, 0));
dp[0][0] = 1;
for (int j = 2; j <= n; j++)
if (p[j-1] == '*') dp[0][j] = dp[0][j-2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (p[j-1] == s[i-1] || p[j-1] == '.') dp[i][j] = dp[i-1][j-1];
else if (p[j-1] == '*') {
dp[i][j] = dp[i][j-2];
if (p[j-2] == s[i-1] || p[j-2] == '.') dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
return dp[m][n];
}
};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[0][0] = true;
for (int j = 2; j <= n; j++)
if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
char pc = p.charAt(j-1), sc = s.charAt(i-1);
if (pc == sc || pc == '.') dp[i][j] = dp[i-1][j-1];
else if (pc == '*') {
dp[i][j] = dp[i][j-2];
char pv = p.charAt(j-2);
if (pv == sc || pv == '.') dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
return dp[m][n];
}
}复杂度
时间复杂度
O(mn)
填 (m+1)×(n+1) 张表，每格 O(1)
空间复杂度
O(mn)
dp 表 (m+1)×(n+1)，可滚动到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 正则表达式匹配 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么 '*' 是难点？+
它能匹配 0 到多个，产生分支：用 0 个就跳过 x*、用多个就消耗 s 一个字符再回头看 x*，二维 DP 合并这两种。
'.' 和 '*' 怎么配合？+
'.*' 表示任意字符任意个数，本质 '.' 被 '*' 重复，转移和普通 'x*' 一样、只是 x 匹配恒成立。
复杂度？+
O(m·n) 时间和空间。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。