好的，我们这次来详细讲解 LeetCode 第 10 题：正则表达式匹配（Regular Expression Matching）。

1. 题目描述

题目链接：LeetCode 10

难度：困难

题目描述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s，而不是部分字符串。

示例：

输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

输入：s = "aa", p = "a*"
输出：true
解释：'*' 表示零个或多个前面的元素，即 'a'。这里匹配 2 个 'a'。

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示零个或多个（'*'）任意字符（'.'）。

输入：s = "aab", p = "c*a*b"
输出：true
解释：'c' 可以出现 0 次，'a' 可以出现 2 次，'b' 出现一次。

2. 题意理解

这个问题是一个简化的正则表达式引擎，只支持两种特殊符号：

• . 相当于通配符，可以代替任何一个字符。
• * 表示它前面的那个字符可以出现 0 次、1 次或多次。

匹配必须覆盖整个字符串 s，而不是部分匹配（即必须 p 能匹配整个 s，而不是 s 的子串）。

关键难点：
* 可以匹配零个或多个，这意味着匹配时存在多种可能的选择（匹配零次、一次、两次…），这需要用 动态规划 或 递归+记忆化 来穷举所有情况。

3. 思路分析：从递归到动态规划

3.1 递归思路（自顶向下）

定义递归函数 match(i, j)：表示 s 从索引 i 开始到末尾的子串，是否能被 p 从索引 j 开始到末尾的模式匹配。

情况分析：

1. 如果 j 到达 p 的末尾：
   此时如果 i 也到达 s 的末尾，则匹配成功；否则失败。

   if j == len(p): return i == len(s)
   

2. 检查第一个字符是否匹配：
   定义 first_match：i 未越界，并且 s[i] 等于 p[j] 或 p[j] == '.'。

   first_match = (i < len(s)) and (p[j] in {s[i], '.'})
   

3. 如果 j+1 未越界且 p[j+1] == '*'：
   这是最复杂的情况，因为 '*' 提供了两种可能：

   • 匹配 0 次：跳过 p[j] 和 '*'，即 match(i, j+2)
   • 匹配 1 次或多次：如果 first_match 为真，则用掉 s 的一个字符，p 位置不变（因为 * 可以继续匹配），即 match(i+1, j)

   所以：

   if j+1 < len(p) and p[j+1] == '*':
        return match(i, j+2) or (first_match and match(i+1, j))
   

4. 如果没有 '*' 跟在后面：
   直接匹配一个字符，然后递归 match(i+1, j+1)。

   else:
        return first_match and match(i+1, j+1)
   

递归树可能很大，会有很多重复计算，所以要用记忆化（缓存 (i, j) 的结果）。

3.2 动态规划思路（自底向上）

我们定义 dp[i][j]：表示 s 的前 i 个字符和 p 的前 j 个字符是否匹配。
这里 i 和 j 表示长度，所以 s[0..i-1] 和 p[0..j-1]。

初始化：

• dp[0][0] = true：两个空字符串匹配。
• 对于 dp[0][j]：空字符串 s 能被 p 匹配，当且仅当 p 的格式是 a*b*c*... 这样成对出现 字符*。

转移方程：

1. 如果 p[j-1] != '*'：
   看 s[i-1] 和 p[j-1] 是否匹配（相等或 p[j-1] == '.'），并且 dp[i-1][j-1] 为真。

   if p[j-1] != '*':
        dp[i][j] = (match_char(s[i-1], p[j-1])) and dp[i-1][j-1]
   

2. 如果 p[j-1] == '*'：
   则 p[j-2] 是 * 前面的字符（记作 x），p[j-2] 和 p[j-1] 是 x* 组合。

   • 匹配 0 次：忽略 x*，dp[i][j] = dp[i][j-2]
   • 匹配 1 次或多次：必须 s[i-1] 和 x 匹配，并且 s 的前 i-1 字符和 p 的前 j 字符匹配（即 x* 继续用），dp[i][j] = match_char(s[i-1], p[j-2]) and dp[i-1][j]

   所以：

   if p[j-1] == '*':
        dp[i][j] = dp[i][j-2] or (match_char(s[i-1], p[j-2]) and dp[i-1][j])
   

其中 match_char(a, b) 为 (b == '.') or (a == b)。

最终结果：dp[len(s)][len(p)]

4. 具体例子推导

以 s = "aab", p = "c*a*b" 为例，我们走一下 DP 表。

初始化 dp[0][0] = true。

先初始化第一行（s 为空）：

• p = "c*"：dp[0][2] = dp[0][0] = true
• p = "c*a"：dp[0][3] = false（因为 a 不能匹配空）
• p = "c*a*"：dp[0][4] = dp[0][2] = true（a* 匹配 0 次）
• p = "c*a*b"：dp[0][5] = false（最后的 b 不能匹配空）

然后逐行计算（i=1..3），最终 dp[3][5] 为 true，匹配成功。

5. 代码实现（动态规划）

def isMatch(s: str, p: str) -> bool:
    m, n = len(s), len(p)
    dp = [[False] * (n + 1) for _ in range(m + 1)]
    
    dp[0][0] = True
    
    # 初始化第一行：s为空，p为a*b*c*...
    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] == '*':
                # 匹配0次
                dp[i][j] = dp[i][j - 2]
                # 匹配1次或多次
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            else:
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
    
    return dp[m][n]

6. 复杂度分析

• 时间复杂度：O(m × n)，m 和 n 分别是 s 和 p 的长度。
• 空间复杂度：O(m × n)，DP 表的大小。

7. 总结

这道题是经典的字符串匹配 + 动态规划问题，关键在于分析 '*' 的两种选择（匹配 0 次或多次），并将这个选择转化为状态转移方程。
递归思路直观但效率低，动态规划通过填表避免了重复计算，是更优的解法。