Regular Expression Matching 是 LeetCode 上一道非常经典的困难题。
这道题要求我们实现一个简单版的正则表达式匹配函数，用来判断字符串 s 是否能够被模式串 p 完整匹配。
这里的模式串只包含两种特殊字符：
-
.：可以匹配任意单个字符 -
*：表示它前面的那个字符可以出现 0 次或多次
注意，这道题要求的是 整个字符串完全匹配，不是子串匹配。
比如：
-
"aa"和"a"不匹配 -
"aa"和"a*"匹配 -
"ab"和".*"匹配
这道题如果直接暴力递归去写，会出现大量重复计算，因此本文采用的解法是：
递归 + 记忆化搜索（Memoization）
这种写法思路清晰，而且非常贴合题目本身的递归结构，是这道题最经典的写法之一。
题目示例
示例 1
输入：s = "aa", p = "a" 输出：false
因为模式串 "a" 只能匹配一个字符，而字符串 "aa" 有两个字符，所以不能完整匹配。
示例 2
输入：s = "aa", p = "a*" 输出：true
因为 * 表示前面的字符 'a' 可以重复出现多次，所以 "a*" 可以匹配 "aa"。
示例 3
输入：s = "ab", p = ".*" 输出：true
因为 . 可以匹配任意字符，* 又表示前面的 . 可以重复多次，所以 ".*" 几乎可以匹配任意字符串。
解题思路
我们可以定义一个函数：
dp(i, j)
表示：
字符串 s 从下标 i 开始的部分，是否能够被模式串 p 从下标 j 开始的部分匹配。
也就是说：
-
dp(0, 0)就是整道题的答案 -
每次递归都只考虑当前这两个位置之后的匹配情况
1. 递归终止条件
如果 j == p.length()，说明模式串已经走完了。
这时候只有一种情况算匹配成功：
i == s.length()
也就是字符串也恰好匹配完了。
2. 先判断当前字符是否匹配
当前字符匹配的条件是：
-
i没有越界 -
并且
p[j] == s[i] -
或者
p[j] == '.'
也就是：
first_match = (i < s.length()) && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')
3. 如果下一个字符是 *
这是本题最核心的地方。
假设当前模式是：
x*
那么它有两种处理方式：
情况一：匹配 0 次
也就是直接跳过这两个字符：
dp(i, j + 2)
情况二：匹配 1 次或多次
前提是当前字符能匹配，也就是 first_match == true。
如果能匹配，那么就让字符串向后走一位，而模式串仍然停在当前 j，因为 x* 还可以继续匹配后面的字符：
dp(i + 1, j)
所以状态转移就是：
dp(i, j) = dp(i, j + 2) || (first_match && dp(i + 1, j))
4. 如果下一个字符不是 *
那就只能老老实实地让当前字符匹配成功，然后一起往后走：
dp(i, j) = first_match && dp(i + 1, j + 1)
Java 代码（带注释）
class Solution {
Boolean[][] memo;
public boolean isMatch(String s, String p) {
// memo[i][j] 表示 dp(i, j) 的计算结果
// 由于结果只有 true / false 两种，但还需要区分“没算过”
// 所以这里用 Boolean 而不是 boolean
memo = new Boolean[s.length() + 1][p.length() + 1];
return dp(0, 0, s, p);
}
public boolean dp(int i, int j, String s, String p) {
// 如果这个状态已经计算过，直接返回
if (memo[i][j] != null) return memo[i][j];
boolean ans;
// 如果模式串已经匹配完，只有当字符串也匹配完才算成功
if (j == p.length()) {
ans = (i == s.length());
} else {
// 判断当前字符是否可以匹配
boolean first_match = (
i < s.length() &&
(p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')
);
// 如果下一个字符是 '*'
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// 两种情况：
// 1. 跳过当前 "x*"，表示匹配 0 次
// 2. 如果当前字符匹配成功，则让 s 往后走一位，p 仍停在 j
ans = dp(i, j + 2, s, p) || (first_match && dp(i + 1, j, s, p));
} else {
// 普通情况：当前字符匹配成功，然后双方都往后移动
ans = first_match && dp(i + 1, j + 1, s, p);
}
}
// 记忆化
memo[i][j] = ans;
return ans;
}
}
代码拆解
这段代码整体不长，但如果第一次接触这道题，还是很容易在细节上绕进去。下面分步骤来看。
1. 为什么 memo 要开成 s.length() + 1 和 p.length() + 1
memo = new Boolean[s.length() + 1][p.length() + 1];
这里多开一位，是因为递归过程中，i 和 j 都有可能走到字符串末尾，也就是：
-
i == s.length() -
j == p.length()
这些位置同样是合法状态，所以数组必须多开一格。
2. dp(i, j) 到底表示什么
这是整道题最关键的定义。
它并不是表示“当前字符是否匹配”，而是表示：
从 s[i...] 和 p[j...] 开始，后面的整段是否匹配。
只要把这个定义想明白，后面的递归就很自然了。
例如：
s = "aab" p = "c*a*b"
当我们进入 dp(0, 0) 时，其实就是在问：
"aab" 能不能被 "c*a*b" 匹配？
后面不断递归，就是不断缩小问题规模。
3. first_match 的作用
boolean first_match = (
i < s.length() &&
(p.charAt(j) == s.charAt(i) || p.charAt(j) == '.')
);
这里表示当前这一个字符能不能对上。
注意顺序不能乱，必须先判断：
i < s.length()
否则当字符串已经走到末尾时，再去访问 s.charAt(i) 就会越界。
4. 为什么遇到 * 要分成两条路
ans = dp(i, j + 2, s, p) || (first_match && dp(i + 1, j, s, p));
这是最核心的一行。
因为 * 的含义就是“前面的字符可以出现 0 次或多次”，所以天然就有两种选择：
第一条路：这个字符一次都不出现
比如：
s = "ab" p = "c*ab"
这里 c* 完全可以不参与匹配，直接跳过去。
所以状态就是：
dp(i, j + 2)
第二条路：当前字符至少匹配一次
比如：
s = "aaa" p = "a*"
只要当前字符能匹配，那么我们就可以消耗掉字符串中的一个字符，但模式串位置不动，因为后面还可能继续匹配更多个 'a'。
所以状态就是：
first_match && dp(i + 1, j)
这其实就是“选或不选”的思想。
5. 普通情况为什么是同时后移一位
ans = first_match && dp(i + 1, j + 1, s, p);
如果后面不是 *，那就没有什么特殊处理了。
当前字符匹配成功之后：
-
字符串往后走一位
-
模式串也往后走一位
这就是最普通的递归匹配过程。
6. 为什么一定要加记忆化
如果不加 memo，这道题会出现非常多的重复子问题。
例如某些位置：
dp(i, j)
可能会从不同递归路径中反复进入。
如果每次都重新算，时间复杂度会非常高，甚至会超时。
加入记忆化之后，每个状态最多只会计算一次，因此效率会提升很多。
执行过程简单演示
以这组数据为例：
s = "aa" p = "a*"
一开始进入：
dp(0, 0)
此时模式串当前位置是 'a'，并且下一个字符是 '*'。
所以分成两种情况：
情况 1：匹配 0 次
dp(0, 2)
此时模式串结束，但字符串还没结束，所以返回 false。
情况 2：匹配至少 1 次
因为当前字符 'a' 能匹配，所以进入：
dp(1, 0)
接下来还能继续匹配，最后会进入：
dp(2, 0) dp(2, 2)
最终 dp(2, 2) 为 true，因此整道题答案就是 true。
复杂度分析
时间复杂度
O(m * n)
其中：
-
m是字符串s的长度 -
n是模式串p的长度
因为记忆化搜索会保证每个状态 (i, j) 只计算一次，而总状态数最多就是 (m + 1) * (n + 1)。
空间复杂度
O(m * n)
主要来自记忆化数组 memo，以及递归调用栈带来的额外开销。
这道题的难点
这道题真正难的地方，不在代码长短，而在于你能不能把状态定义清楚。
它有两个最容易卡住的点：
-
dp(i, j)的含义到底是什么 -
遇到
*时为什么要拆成两种情况
而且这道题非常适合拿来训练递归思维，因为它天然就是一个“把大问题拆成更小子问题”的过程。
总结
这道题的核心思想其实可以概括成一句话：
从当前位置出发，讨论当前字符能不能匹配；如果遇到 *，就考虑“跳过”或者“继续使用”两种选择。
所以整道题的解题步骤就是：
-
定义
dp(i, j)表示后缀匹配问题 -
判断当前字符是否匹配
-
如果下一个字符是
*，分两种情况递归 -
如果不是
*，就正常向后推进 -
用
memo记录已经算过的状态，避免重复计算
这也是这道题最经典、最推荐掌握的一种写法。
如果你刚开始接触动态规划或者记忆化搜索，这道题其实非常值得反复理解一遍。 因为它不仅仅是在考“正则表达式”，更是在考你对 状态设计、递归转移、边界处理 的掌握程度。
