线性动态规划：正则表达式匹配（Regular Expression Matching）

题目描述

给定一个字符串 s 和一个模式串 p，实现一个支持 . 和 * 的正则表达式匹配。其中：

• . 匹配任意单个字符。
• * 匹配零个或多个前面的那个元素。
  匹配应该覆盖整个字符串 s，而不是部分字符串。

示例：

• 输入：s = "aa", p = "a"，输出：false（因为模式只能匹配一个字符 "a"，而字符串有两个 "a"）。
• 输入：s = "aa", p = "a*"，输出：true（因为 * 可以让前面的 'a' 出现零次或多次，这里匹配两次）。
• 输入：s = "ab", p = ".*"，输出：true（因为 .* 表示零个或多个任意字符，这里匹配 "ab"）。

要求：设计一个动态规划算法，判断 s 是否与 p 完全匹配。

解题思路

这个问题看似复杂，但通过分析模式和字符串的匹配方式，我们可以建立一个二维动态规划表来逐步求解。核心思想是定义状态 dp[i][j] 表示 s 的前 i 个字符（s[0:i-1]）是否与 p 的前 j 个字符（p[0:j-1]）匹配。

匹配规则总结：

1. 如果 p[j-1] 是普通字符（不是 . 或 *），则必须 s[i-1] == p[j-1] 且 dp[i-1][j-1] 为真。
2. 如果 p[j-1] 是 .，则 s[i-1] 可以是任意字符，只需要 dp[i-1][j-1] 为真。
3. 如果 p[j-1] 是 *，则情况更复杂，因为它和前面的字符 p[j-2] 一起使用。分为两种情况：
   • 匹配零个字符：即忽略 p[j-2] 和 *，那么 dp[i][j] 的真假取决于 dp[i][j-2]。
   • 匹配一个或多个字符：这需要 s[i-1] 和 p[j-2] 匹配（即 s[i-1] == p[j-2] 或 p[j-2] == '.'），并且 dp[i-1][j] 为真（表示前面的字符已经匹配了 s[i-1] 之前的字符，现在再多匹配一个 s[i-1]）。

动态规划步骤详解

1. 定义状态
   设 dp[i][j] 表示字符串 s 的前 i 个字符（s[0...i-1]）是否与模式 p 的前 j 个字符（p[0...j-1]）匹配。

   • i 的范围从 0 到 len(s)，j 的范围从 0 到 len(p)。
   • 当 i=0 且 j=0 时，表示空字符串和空模式匹配，即 dp[0][0] = True。

2. 初始化

   • dp[0][0] = True：空字符串匹配空模式。
   • 对于 j>0 的情况，我们需要初始化 dp[0][j]，即空字符串是否匹配模式 p[0:j-1]。只有当模式由类似 a* 这样的组合组成时，空字符串才可能匹配。具体规则：
     • 如果 p[j-1] 是 *，那么可以忽略它和它前面的字符，即 dp[0][j] = dp[0][j-2]。
     • 否则，dp[0][j] = False。

3. 状态转移方程
   对于 i>0 和 j>0：

   • 如果 p[j-1] != '*'：
     • 如果 s[i-1] == p[j-1] 或 p[j-1] == '.'，那么 dp[i][j] = dp[i-1][j-1]（当前字符匹配，看之前是否匹配）。
     • 否则 dp[i][j] = False。
   • 如果 p[j-1] == '*'：
     • 情况1：* 匹配零个前面的字符。即忽略 p[j-2] 和 *，那么 dp[i][j] = dp[i][j-2]。
     • 情况2：* 匹配一个或多个前面的字符。这要求 s[i-1] 和 p[j-2] 匹配（即 s[i-1] == p[j-2] 或 p[j-2] == '.'），并且 dp[i-1][j] 为真（表示 s[0:i-2] 已经匹配了 p[0:j-1]，现在再多匹配一个 s[i-1]）。
     • 综合两种情况：dp[i][j] = dp[i][j-2] or (dp[i-1][j] and (s[i-1] == p[j-2] or p[j-2] == '.'))。

4. 填表顺序
   由于 dp[i][j] 依赖于 dp[i-1][j-1]、dp[i][j-2] 或 dp[i-1][j]，我们可以按行从上到下、每行从左到右填表。

5. 最终答案
   填完整个表后，dp[len(s)][len(p)] 就是最终答案，表示整个字符串 s 是否与整个模式 p 匹配。

举例说明

以 s="aa"，p="a*" 为例：

• 初始化：dp[0][0]=True，dp[0][1]=False（因为 p[0]='a' 不是 *），dp[0][2]=dp[0][0]=True（因为 p[1]='*'，匹配零个前面的字符 'a'）。
• 填表：
  • dp[1][1]：p[0]='a' 不是 *，且 s[0]='a' 匹配 p[0]，所以 dp[1][1]=dp[0][0]=True。
  • dp[1][2]：p[1]='*'，有两种情况：
    1. 匹配零个 'a'：dp[1][0]=False，忽略。
    2. 匹配一个或多个 'a'：要求 s[0] 和 p[0] 匹配（成立），且 dp[0][2]=True，所以 dp[1][2]=True。
  • dp[2][1]：p[0]='a' 不是 *，但 s[1]='a' 匹配 p[0]，且 dp[1][0]=False，所以 dp[2][1]=False。
  • dp[2][2]：p[1]='*'，两种情况：
    1. 匹配零个 'a'：dp[2][0]=False。
    2. 匹配一个或多个 'a'：要求 s[1] 和 p[0] 匹配（成立），且 dp[1][2]=True，所以 dp[2][2]=True。
• 最终 dp[2][2]=True，匹配成功。

算法复杂度

• 时间复杂度：O(m*n)，其中 m 是字符串 s 的长度，n 是模式 p 的长度。因为我们需要填充一个 (m+1)×(n+1) 的表格。
• 空间复杂度：O(m*n)，用于存储动态规划表。可以优化到 O(n) 使用滚动数组，但为了清晰理解，这里展示完整表格。

代码实现（Python示例）

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

    # 初始化空字符串匹配模式的情况
    for j in range(1, 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] != '*':
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
            else:
                # 匹配零个字符
                dp[i][j] = dp[i][j - 2]
                # 匹配一个或多个字符
                if p[j - 2] == s[i - 1] or p[j - 2] == '.':
                    dp[i][j] = dp[i][j] or dp[i - 1][j]

    return dp[m][n]

这个算法系统地考虑了所有匹配可能性，通过状态转移逐步推导出最终结果。你可以尝试用不同例子（如 s="ab", p=".*"）来验证每一步的逻辑。