题目

题目描述详见：10. 正则表达式匹配 - 力扣（LeetCode）

题解

📝 写在前面

之前的题目，或许我不知道快速的、巧妙的解法，但我可以用笨方法，或者说“朴素”的方法是手搓出来。

但这道题我甚至是思路全无，无从下笔，所以特地来记录一下题解思路。

💡 参考
本文的题解来自官方题解

正如本题题目 ”正则表达式匹配” 所说，这是一个逐步匹配的过程。

我们记字符串 $s$ ，字符规律 $p$ 。对于字符规律 $p$ ，它包含以下几类字符：

  • 普通字符

  • '.'：匹配任意单个字符

  • '*'：匹配零个或多个前面的那一个元素

事实上，我们可以进一步分为两类：（1）字符（2）星号。

我们每次从字符串 $p$ 取出一个 字符 或 字符+星号 的组合：

  • 对于 $p$ 中的一个字符，它只能在 $s$ 中匹配一个字符，匹配方法具有唯一性；

  • 对于 p 中字符+星号的组合，它可以在 s 中匹配任意自然数个字符，不具有唯一性。

因此我们可以考虑使用动态规划，对匹配的方案进行枚举。

💡 说明
唯一性？

关于这里的“唯一性”，指的是匹配方式是否确定。

对于字符+星号的组合，由于星号可以匹配0个或多个元素，因此单纯看这个组合是无法确定匹配方式的。

下面是一个例子，单个字符的匹配是唯一确定的，字符+组合则相反：

模式 面对字符 a 匹配方式 是否唯一
a a 只能匹配这 1 个 a，然后双双后移 ✅ 唯一
. a 只能匹配这 1 个 a，然后双双后移 ✅ 唯一
a* aaa 可以匹配 0 个、1 个、2 个、3 个 a ❌ 不唯一
动态规划？

可以这样理解，因为 * 带来了分支，我们必须尝试所有的分支，才能知道是否存在一个完美的匹配方案。

下面的例子很好地说明了这个问题：

1
2

s = "aaab"
p = "a*aab"

处理 p 的 a* 时，面对 s 开头的 "aaa"，a* 有多种选择：

  • 匹配 0 个 a → 剩余 s="aaab"，p="aab"

  • 匹配 1 个 a → 剩余 s="aab"，p="aab"

  • 匹配 2 个 a → 剩余 s="ab"，p="aab"

  • 匹配 3 个 a → 剩余 s="b"，p="aab"

注意，单纯看 a* 而不考虑 s 的其他部分，这里的匹配方式都是合法的。

但题目希望找到的是覆盖整个输入字符串的匹配，因此这里的匹配方法只有1个是能够完全匹配的。

那么要找出合适的匹配，显然的想法就是需要枚举所有匹配方案。又因为枚举过程中存在大量重叠子问题，所以我们考虑使用动态规划。

🚨 易错点

根据题解的描述分析，a* 应该看成一个整体。

也就是说，a* 这个整体可以啥都不匹配，也就是前面说的匹配 0 个字符，而不是说前面的 a 必须要单独匹配一个字符。

我们用 $f[i][j]$ 表示 $s$ 的前 $i$ 个字符与 $p$ 中的前 $j$ 个字符是否能够匹配。

在进行状态转移时，我们考虑 $p$ 的第 $j$ 个字符的匹配情况：

  • 如果 $p$ 的第 $j$ 个字符是一个小写字母，那么我们必须在 $s$ 中匹配一个相同的小写字母。

    转移方程如下：

    $$ f[i][j] = \begin{cases} f[i-1][j-1], & s[i] = p[j] \\ \text{false}, & s[i] \neq p[j] \end{cases} $$

    这里解释一下（后面讨论的前提是：$p$ 的第 $j$ 个字符是一个小写字母）：

    如果 $s$ 的第 $i$ 个字符和 $p$ 的第 $j$ 个字符不相同，那么无法匹配；否则可以匹配两个字符串的最后一个字符，完整的匹配结果取决于两个字符串前面的部分。

  • 如果 $p$ 的第 $j$ 个字符是 * ，那么就表示我们可以对 $p$ 的第 $j-1$ 个字符串匹配任意自然数次。

    在匹配 0 次的情况下，我们有

    $$ f[i][j] = f[i][j-2] $$

    也就是没有匹配 $s$ 中的字符。

    同理，在匹配 1,2,3,… 次的情况下，类似的有：

    $$ \begin{align*} f[i][j] &= f[i-1][j-2], &&\text{if } s[i] = p[j-1] \\ f[i][j] &= f[i-2][j-2], &&\text{if } s[i-1] = s[i] = p[j-1] \\ f[i][j] &= f[i-3][j-2], &&\text{if } s[i-2] = s[i-1] = s[i] = p[j-1] \\ \end{align*}\\ \cdots $$

    显然，理论上我们可以一直这样写下去，这就又需要枚举这个组合到底匹配了 s 中的几个字符，代码编写麻烦的同时，会影响时间复杂度。

    这里，我们要换个角度思考问题：字母 + 星号的组合在匹配过程中，本质只有两个情况：

    1. 匹配 $s$ 末尾的一个字符，将该字符扔掉，而该组合还可以继续匹配；

    2. 不匹配字符，将该组合扔掉，不再进行匹配。

    表达成转移方程如下：

    $$ f[i][j] = \begin{cases} f[i-1][j] \text{ or } f[i][j-2], & s[i] = p[j-1] \\ f[i][j-2], & s[i] \neq p[j-1] \end{cases} $$
    💡 状态转移方程说明

    官方题解称这个状态转移方程是 “很精巧的”。

    不幸的是，它也是很难理解的。这里展开讲讲：

    上面提到了匹配过程本质只有两个情况：

    第一种情况，x* 匹配至少 1 个字符

    要满足这个情况，s 的最后一个字符要能够被 x 匹配。

    p[j] 是 *， p[j-1] 也就是 x，这种情况也就可以表示为 s[i] = p[j-1]

    如果匹配 1 个字符，s 末尾会少一个，但 x* 仍然保留，因为可以继续匹配，所以有状态转移方程：

    1

    f[i][j] = f[i-1][j]    # 这里是 j 而不是 j-2，因为 x* 还可以继续匹配

    第二种情况，x* 匹配 0 个字符

    此时，直接把这个组合扔掉，也就是让 x* 匹配 0 个字符。

    当前的匹配的结果取决于前面能不能匹配。

    1

    f[i][j] = f[i][j-2]

    下面还是用例子来说明：

    假设输入 s="aaa"，p="a*"：

    1. a* 先匹配 s 末尾的 1 个 a （第 3 个 a）

      剩余问题变成："aa" 和 "a*" 能匹配吗？ → f[2][2]

    2. a* 再匹配 s 末尾的 1个 a （第 2 个 a）

      剩余问题变成："a" 和 "a*" 能匹配吗？ → f[1][2]

    3. a* 再匹配 s 末尾的 1个 a （第 1 个 a）

      剩余问题变成："" 和 "a*" 能匹配吗？ → f[0][2]

    4. f[0][2]：a* 匹配 0 个 a，跳过这个组合

      变成 "" 和 "" 匹配 → true

    我们回过头看看这个流程，匹配 3 个 a 不是一次性决定的，而是每次只决定匹配 1 个，然后递归交给 f[i-1][j] 继续处理。如果 f[i-1][j] 还需要匹配，它自己会继续调用 f[i-2][j] ，知道某一步选择“匹配 0 个”（f[i][j-2]）为止。

    举这个例子的意义在于，说明并理解清楚，目前的思路是把 “匹配多次“ 拆成 ”先匹配1次，剩下的交给子问题递归处理“

    所以前面提到的转移方程，也就是分别对应这两个情况。

    但值得一提的，为什么可以匹配的时候（s[i] = p[j-1]），匹配状态还要考虑 f[i][j-2]，也就是不使用 x* 的情况？

    这里需要说明，局部匹配成功不等于全局匹配成功。因为我们需要枚举所有的情况，对于 x* 的匹配，并不是说可以匹配就一定要匹配。

    为了考虑到所有情况，我们同样可以选择不使用这个组合。这是合法的情况，也是我们必须考虑的。

    📝 待补充

    对于前面说明的最后，提到的特殊情况（可以匹配但不匹配），肯定有实际例子可以说明。

    但现在还没有想到，后面要补充在这里。

  • 在任意情况下，只要 $p[j]$ 是 .，那么 $p[j]$ 一定成功匹配 $s$ 中的任意一个小写字母。

综上所述，我们终于可以得出完整的状态转移方程：

$$ f[i][j] = \begin{cases} \text{if } (p[j] \neq \text{`}\ast\text{'}) = \begin{cases} f[i-1][j-1], & \text{matches}(s[i], p[j]) \\ \text{false}, & \text{otherwise} \end{cases} \\ \text{otherwise} = \begin{cases} f[i-1][j] \text{ or } f[i][j-2], & \text{if } \text{matches}(s[i], p[j-1]) \\ f[i][j-2], & \text{otherwise} \end{cases} \end{cases} $$

对于 $\text{matches}(x,y)$ ，它是判断两个字符是否匹配的辅助函数：

$$ \text{matches(x,y)} = \begin{cases} \text{true}, & y = \text{`.'} \text{ or } x = y \\ \text{false}, & \text{otherwise} \end{cases} $$
✅ 学习点

这里提取一个函数，来抽象会多次用到的单字符匹配过程。

这一点我在写题时候也有想到，就类似 C++ 中的重载运算符，可惜只停留在想法，没有付诸实践。这里的思路非常值得学习。

这里，动态规划的边界条件是 $f[0][0]=\text{true}$ ，即两个空字符串是可以匹配的。

最后的输出是 $f[m][n]$，其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $p$ 的长度。

下面是官方题解中给出的思考题，之后有空解答一下：

📝 思考题

在上面的状态转移方程中，如果字符串 $p$ 中包含一个「字符 + 星号」的组合（例如 a*），那么在进行状态转移时，会先将 a 进行匹配（当 $p[j]$ 为 a 时），再将 a* 作为整体进行匹配（当 $p[j]$ 为 * 时）。

然而，在题目描述中，我们必须将 a* 看成一个整体，因此将 a 进行匹配是不符合题目要求的。

看来我们进行了额外的状态转移，这样会对最终的答案产生影响吗？

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)

        def matches(i: int, j: int) -> bool:
            if i == 0:   # s 的前 0 个字符的匹配情况，相当于空串，肯定匹配不了
                return False
            if p[j-1] == '.':
                return True
            return s[i - 1] == p[j - 1]

        f = [[False] * (n+1) for _ in range(m+1)]
        f[0][0] = True
        for i in range(m+1):
            for j in range(1, n+1):
                if p[j-1] == '*':
                    f[i][j] |= f[i][j-2]    # * 匹配 0 次    
                    # 等价于 f[i][j] = f[i][j] | f[i][j-2]
                    if matches(i, j-1):
                        f[i][j] |= f[i-1][j]    # * 匹配至少 1 次成功
                
                # 这里为什么不用赋值?
                # 在有 * 的情况有多种，我们不希望第二种情况覆盖掉第一种，而是希望累加(or)

                else:
                    if matches(i, j):
                        f[i][j] |= f[i-1][j-1]
        
        return f[m][n]