好的，我们接下来学习 LeetCode 第 10 题：正则表达式匹配。

1. 题目描述

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

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

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

示例 1：

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

示例 2：

输入：s = "aa", p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

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

提示：

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s 只包含从 a-z 的小写字母。
• p 只包含从 a-z 的小写字母，以及字符 . 和 *。
• 保证每次出现字符 * 时，前面都匹配到有一个有效字符。

2. 初步思路

这个问题难点在于 '*' 可以匹配 0 次 或 多次 前面的字符，这导致有多种匹配可能性。

例如 s = "aaa", p = "a*a"：

• "a*" 可以匹配 "aaa" 的前两个 'a'，然后 p 剩下的 'a' 匹配最后一个 'a'。
• 或者 "a*" 匹配 "aaa" 的前三个 'a'，但 p 剩下的 'a' 无法匹配（因为 s 用完了），这就不行。
• 或者 "a*" 匹配 0 次 'a'，那么 p = "a*a" 就变成 "aa" 去匹配 "aaa"，显然不行。

所以我们需要尝试所有可能性，这提示用 动态规划（DP） 或 递归+记忆化。

3. 定义 DP 状态

设 dp[i][j] 表示：s 的前 i 个字符 与 p 的前 j 个字符 是否匹配。

• i 和 j 表示长度，即 s[0..i-1] 和 p[0..j-1]。
• 最终答案是 dp[m][n]，其中 m = s.length, n = p.length。

4. 状态转移方程

我们需要考虑 p 的第 j 个字符（即 p[j-1]）的情况：

情况 1：p[j-1] 是普通字母（不是 '*'）

• 那么必须 s[i-1] == p[j-1] 才能匹配。
• 并且 s 的前 i-1 个字符与 p 的前 j-1 个字符也要匹配。
• 即：
  如果 p[j-1] 不是 '*' 且不是 '.'：
  dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1])

情况 2：p[j-1] 是 '.'

• '.' 可以匹配任意单个字符，所以只要 s 还有字符，这里就能匹配。
• 并且 s 的前 i-1 个字符与 p 的前 j-1 个字符也要匹配。
• 即：
  如果 p[j-1] == '.'：
  dp[i][j] = dp[i-1][j-1]

情况 3：p[j-1] 是 '*'（重点）

这时 p[j-2] 是 '*' 前面的字符，记作 char（可能是字母或 .）。

'*' 表示匹配 0 次或多次 char。

子情况 3.1：匹配 0 次

• 即忽略 p 的 char* 这两个字符（p 中 j-2 和 j-1 位置）。
• 那么 dp[i][j] = dp[i][j-2]

子情况 3.2：匹配 1 次或多次

• 前提是 s[i-1] 必须与 char 匹配（即 char == '.' 或 char == s[i-1]）。
• 如果匹配了 s[i-1]，那么 s 的前 i-1 个字符应当与 p 的前 j 个字符匹配（因为 '*' 可以继续匹配前面的字符）。
• 即 dp[i][j] = dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.')

合并两种情况：
dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))

注意：匹配多次的情况被 dp[i-1][j] 隐含了，因为从 i-1 到 i 时仍然用同一个 j（即 '*' 模式还在继续匹配）。

5. 初始条件

• dp[0][0] = true：两个空字符串匹配。
• 对于 i = 0（s 为空）但 j > 0：
  只有当 p 的形如 a*b*c* 这样每个带 '*' 的字符都匹配 0 次时才可能为 true。
  具体：如果 p[j-1] == '*'，则 dp[0][j] = dp[0][j-2]，否则为 false。
• 对于 j = 0 且 i > 0：dp[i][0] = false（空模式无法匹配非空字符串）。

6. 计算顺序

按 i 从 0 到 m，j 从 1 到 n（j=0 时只有 i=0 为 true，其余 false，可先初始化）。

7. 示例推导

s = "aa", p = "a*"

• m=2, n=2
• 初始化 dp[0][0] = true
• j=1：p[0]='a' 不是 '*'，所以 i=0 时 dp[0][1] = false（空 s 无法匹配 "a"）
• j=2：p[1]='*'，char = p[0]='a'
  • i=0：匹配 0 次：dp[0][2] = dp[0][0] = true
  • i=1：
    • 匹配 0 次：dp[1][0] 不存在？不对，是 dp[1][2] = dp[1][0] or ... 但 dp[1][0] 是 false。
      匹配 1 次以上：dp[0][2] and (s[0]=='a'=='a') → true and true → true。
      所以 dp[1][2] = false or true = true
  • i=2：
    • 匹配 0 次：dp[2][0]=false
      匹配 1 次以上：dp[1][2] and (s[1]=='a'=='a') → true and true → true
      所以 dp[2][2] = false or true = true

最终 dp[2][2] = true，匹配。

8. 代码实现（思路）

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的情况
    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] == '.' or p[j - 2] == s[i - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j]
            elif p[j - 1] == '.':
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1])
    
    return dp[m][n]

9. 总结

• 核心是处理 '*' 的两种选择：匹配 0 次或匹配 1 次以上。
• 匹配 1 次以上的情况可以通过 dp[i-1][j] 来递归包含多次匹配。
• 初始条件要注意空串与模式的匹配情况。
• 时间复杂度 O(mn)，空间复杂度 O(mn)。