BM76　正则表达式匹配¶

较难通过率 27.23%python3核心代码模式样例通过牛客 AC字符串递归动态规划

牛客原题　源码

讲解章节：线性 DP

一句话

二维布尔 DP，星号分「一次不用」与「再多用一次」两条路。

解题思路¶

这题考什么¶

把「星号可以重复任意次（含 0 次）」这种不定长的匹配，化成每一步只做二选一的转移——这正是 DP 相对暴力回溯的价值所在。

状态定义：dp[i][j] = str 的前 i 个字符能否与 pattern 的前 j 个字符完全匹配。边界：

dp[0][0] = True                             两个空串互相匹配
dp[0][j] = dp[0][j-2]   当 p[j-1] == '*'    形如 "a*b*c*" 的模式才能匹配空串
dp[i][0] = False (i > 0)                    空模式匹配不了非空串，由初值全 False 自动成立

转移方程，记 c = pattern[j-1]：

c 不是 '*'（普通字母或 '.'）：
    dp[i][j] = dp[i-1][j-1] and (c == '.' or c == str[i-1])

c 是 '*'（它与前一个字符 pc = pattern[j-2] 捆成一个整体 "pc*"）：
    dp[i][j] = dp[i][j-2]                                      整块用 0 次
               or (dp[i-1][j] and (pc == '.' or pc == str[i-1]))   再吃掉一个 str[i-1]

第一条是把 "pc*" 整块跳过；第二条是「这一整块已经匹配到 str 的前 i-1 位，如果当前字符 str[i-1] 也能被 pc 覆盖，就让星号再重复一次」。注意星号永远不单独看，必须与前一个字符捆绑成一个可重复单元。答案是 dp[m][n]。

数据规模与复杂度¶

|str| <= 26，|pattern| <= 26，str 只含小写字母，pattern 另可含 '.' 与 ''，且题面保证没有连续的 ''；时限 2 秒（其他语言）。表格至多 27 * 27 = 729 格，时间 O(mn)、空间 O(mn)。行只依赖上一行与本行左边，压成一维也行，但规模这么小时二维表更好读，不必省。被否决的写法是纯回溯：每遇到一个星号就分裂出「用 0 次 / 用 1 次 / 用 2 次 ...」的分支， "aaaaa..." 配 "aaaa..." 这类数据会指数级爆炸，而 DP 把重复的子问题合并掉了。

坑在哪¶

星号可以匹配空串，这是全题的核心。少了 dp[0][j] 的预处理， "" 配 "a" 会答成 False，"aaa" 配 "abaca" 也会因为中间的 "b" 用 0 次而失配。
匹配是整串匹配而不是部分匹配，所以答案取 dp[m][n]，不能一发现某个前缀匹配就返回 True；"aaa" 与 "aa.a" 不匹配正是因为长度对不上。
星号必须与前一个字符捆绑，j 至少为 2。题面保证没有连续的 ''，也隐含模式不以 '' 开头；若模式真以 '*' 开头，p[j-2] 会取成 p[-1]， Python 的负下标不报错，只会悄悄拿串尾字符去比，结果无意义。实测数据不含这种模式。
空串边界的循环从 j = 2 起步，而且判的是 p[j-1] == '*' 时取 dp[0][j-2]。从 j = 1 起步会让 j-2 变成 -1，绕到行尾取到无关的值。
星号那条转移里的 dp[i-1][j] 用的是同一列（星号块原封不动）而不是 j-1 或 j-2：重复一次消耗的是 str 的一个字符，不是 pattern 的。写成 prev[j-1] 会把星号退化成 '.'。
官方模板把第一个参数命名为 str，遮蔽了内建类型名。签名不能改，所以函数内先取 s、p 两个短别名，既避开误用 str() 的风险，也省掉内层的属性查找。

样例复核¶

"aaa" 配 "aa"：dp[0][2] = True（"a" 用 0 次），星号一路吃掉前两个 'a'，最后一列的普通字符 'a' 对上第三个 'a'，dp[3][3] = True，与期望输出一致。

参考实现¶

solutions/nowcoder/BM76/sol.py
from typing import List, Optional


class Solution:
    def match(self, str: str, pattern: str) -> bool:
        # 参数名 str 由官方模板固定（会遮蔽内建类型），这里取短别名再用
        s, p = str, pattern
        m, n = len(s), len(p)

        # dp[i][j]：s[:i] 与 p[:j] 是否完全匹配。全 False 的初值直接给出边界
        # dp[i][0] = False（i > 0）：空模式匹配不了非空串
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        # 空串这一行要单独铺：只有 "x*y*z*" 这种整块可省的模式才匹配得上空串。
        # 从 j = 2 起步是因为星号必须与前一个字符捆绑，j-2 不能是负下标
        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):
            si = s[i - 1]                   # 本轮固定的待匹配字符
            row, prev = dp[i], dp[i - 1]    # 行引用提前绑定，省掉内层的二次下标
            for j in range(1, n + 1):
                c = p[j - 1]
                if c == "*":
                    pc = p[j - 2]           # 星号总是与前一个字符捆成一个可重复单元
                    # ① row[j-2]："pc*" 整块用 0 次，跳过它；
                    # ② prev[j]：星号块保持不变（列不动），再重复一次吃掉 si
                    row[j] = row[j - 2] or (prev[j] and (pc == "." or pc == si))
                else:
                    # 普通字符或 '.'：各消耗一个字符，退回左上角的子问题
                    row[j] = prev[j - 1] and (c == "." or c == si)
        return dp[m][n]                     # 整串匹配，取右下角

BM76 正则表达式匹配¶