10. 正则表达式匹配

发表于 分类于 阅读次数： Waline： 本文字数： 885 阅读时长 ≈ 3 分钟

考点

  • LCS
  • 初始值、状态转移设计

思路

一、问题概述

给定字符串 s 与模式串 p，判断 p 是否能够完全匹配 s。

模式串仅包含三类字符：

  • 普通字符（如 a、b）
  • 通配符 .：可匹配任意单个字符
  • 修饰符 *：表示其前一个字符可以出现 0 次或任意多次

需要注意的是：

* 不是一个独立字符，它始终与其前一个字符构成一个整体（如 a*、.*）。

二、动态规划建模

1. 状态定义

定义二维 DP 数组： \[ f[i][j] = \begin{cases} \text{true} & \text{若 } s[0..i-1] \text{ 能匹配 } p[0..j-1] \\ \text{false} & \text{否则} \end{cases} \] 其中：

  • \(i \in [0, |s|]\)
  • \(j \in [0, |p|]\)

这是前缀匹配型 DP，而不是“是否出现子串”。

三、初始化的关键难点（本题最易出错点）

1. 基础状态

\[ f[0][0] = \text{true} \]

空字符串与空模式串显然匹配。

2. 空字符串 vs 非空模式串

这是整道题最容易出错的地方。

空字符串 并不能 匹配任意模式串，例如：

  • "" ❌ "a"
  • "" ❌ "abc"

但以下情况是合法的：

  • "" ✅ "a*"
  • "" ✅ "a*b*c*"

也就是说：

空字符串并不能匹配任意模式前缀。只有当模式前缀可以完全由若干个 t* 片段拼接而成（其中 t 为普通字符或 .）时，空字符串才可能匹配该前缀。例如 "" 可匹配 c*、a*b*c*、.*，但不能匹配 a、ab、.*a。

因此初始化第 0 行时，必须严格遵循 * 的语义： \[ f[0][j] = \begin{cases} f[0][j-2] & \text{若 } p[j-1] = '*' \\ \text{false} & \text{否则} \end{cases} \] 对应代码：

1
2
3
for (int j = 2; j <= n2; ++j)
    if (p[j - 1] == '*')
        f[0][j] = f[0][j - 2];

绝不能把整行 f[0][j] 初始化为 true，否则会导致例如：

1
2
s = "aaa"
p = "aaaa"

被错误判为 true。

四、状态转移方程设计

1. 普通字符 / 点号 .

当 p[j-1] 是普通字符，或 .：

若满足 p[j-1] = s[i-1] 或 p[j-1] = '.'，则： \[ f[i][j] = f[i-1][j-1] \] 含义：当前字符成功匹配，问题规模缩小为前一位。

2. 星号 *（核心难点）

设 p[j-1] == '*'，则其修饰字符为 p[j-2]。

情况一：x* 匹配 0 次

直接忽略 x* 这两个字符： \[ f[i][j] = f[i][j-2] \]

情况二：x* 匹配 ≥ 1 次

前提：x 能匹配 s[i-1]，即 p[j-2] = s[i-1] 或 p[j-2] = '.'。

此时： \[ f[i][j] = f[i-1][j] \] 含义：当前字符被 x* 吸收，模式串仍可继续使用 *。

3. 综合转移公式

\[ f[i][j] = \begin{cases} f[i-1][j-1] & \text{若字符或 '.' 匹配} \\ f[i][j-2] \lor f[i-1][j] & \text{若 } p[j-1]='*' \text{ 且前字符可匹配} \end{cases} \]

五、算法复杂度分析

  • 时间复杂度：

\[ O(|s|\cdot|p|) \]

  • 空间复杂度：

\[ O(|s|\cdot|p|) \]

在本题限制（长度 ≤ 20）下完全可行。

六、完整 AC 代码（附录）

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
30
31
32
33
34
35
class Solution {
public:
    static const int maxn = 25;
    bool isMatch(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        bool f[maxn][maxn];
        memset(f, 0, sizeof(f));

        // 空串匹配空模式
        f[0][0] = 1;

        // 初始化：空串 vs 模式前缀
        for (int i = 2; i <= n2; ++i)
            if (p[i - 1] == '*')
                f[0][i] = f[0][i - 2];

        // DP 转移
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (s[i - 1] == p[j - 1])
                    f[i][j] |= f[i - 1][j - 1];
                else if (p[j - 1] == '.')
                    f[i][j] |= f[i - 1][j - 1];
                else if (p[j - 1] == '*') {
                    // 匹配 0 次
                    f[i][j] |= f[i][j - 2];
                    // 匹配 >=1 次
                    if (p[j - 2] == '.' || p[j - 2] == s[i - 1])
                        f[i][j] |= f[i - 1][j];
                }
            }
        }
        return f[n1][n2];
    }
};