44. 通配符匹配

发表于 2025-12-19 分类于力扣阅读次数： Waline：本文字数： 686 阅读时长 ≈ 2 分钟

考点

LCS
初始值设置、状态设计

思路

一、问题描述

给定字符串 s 与模式串 p，其中：

? 可以匹配任意 单个字符
* 可以匹配任意 长度（包含 0） 的字符串

判断 p 是否可以完整匹配 s。

二、动态规划建模

1. 状态定义

设： \[ f[i][j] = \text{模式串 } p \text{ 的前 } j \text{ 个字符，是否能匹配字符串 } s \text{ 的前 } i \text{ 个字符} \] 其中：

\(0 \le i \le |s|\)
\(0 \le j \le |p|\)

最终答案为： \[ \boxed{f[|s|][|p|]} \]

2. 初始条件（边界处理，最容易出错）

（1）空串匹配空模式

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

（2）空字符串匹配模式串前缀

当 \(i = 0\) 时，只有当模式前缀全部由 \* 构成，才能匹配空串： \[ f[0][j] = \begin{cases} f[0][j-1], & p[j-1] = '*' \\ \text{false}, & \text{otherwise} \end{cases} \] 该初始化非常关键，遗漏会导致大量边界错误。

（3）非空字符串匹配空模式

\[ f[i][0] = \text{false}, \quad i \ge 1 \]

三、状态转移方程

对于 \(i \ge 1, j \ge 1\)，分三类讨论：

1️⃣ 普通字符或 `?`

当：

\(p[j-1] = s[i-1]\)，或
\(p[j-1] = '?'\)

则二者各消耗一个字符： \[ f[i][j] = f[i-1][j-1] \]

2️⃣ 星号 `*`

* 可以匹配 空串或非空串，因此有两种转移来源：

匹配 0 个字符： \[ f[i][j] \leftarrow f[i][j-1] \]
匹配 至少 1 个字符： \[ f[i][j] \leftarrow f[i-1][j] \]

综合得： \[ f[i][j] = f[i-1][j] \lor f[i][j-1] \]

3️⃣ 其余情况

无法匹配： \[ f[i][j] = \text{false} \]

四、空间优化（滚动数组）

观察转移方程可知：

当前行 f[i][*]只依赖：
- 上一行 f[i-1][*]
- 当前行左侧 f[i][j-1]

因此可将二维数组压缩为 两行滚动数组： \[ f[2][|p| + 1] \] 关键注意点：

每一轮 \(i\) 开始时，必须显式清空当前行，否则会错误继承两轮前的残留状态。

五、时间与空间复杂度

时间复杂度： \[ O(|s| \cdot |p|) \]
空间复杂度（滚动数组）： \[ O(|p|) \]

六、参考实现（AC 代码）

class Solution {
public:
    static const int maxn = 2000 + 5;
    bool isMatch(string s, string p) {
        int n1 = s.size(), n2 = p.size();
        bool f[2][maxn];
        memset(f, 0, sizeof(f));

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

        // 空串匹配模式前缀
        for (int j = 1; j <= n2; ++j)
            f[0][j] = f[0][j - 1] & (p[j - 1] == '*');

        for (int i = 1; i <= n1; ++i) {
            f[i & 1][0] = 0; // 非空串无法匹配空模式
            for (int j = 1; j <= n2; ++j) {
                f[i & 1][j] = 0; // 清当前格子
                if (s[i - 1] == p[j - 1])
                    f[i & 1][j] = f[(i - 1) & 1][j - 1];
                else if (p[j - 1] == '?')
                    f[i & 1][j] = f[(i - 1) & 1][j - 1];
                else if (p[j - 1] == '*')
                    f[i & 1][j] = f[(i - 1) & 1][j] | f[i & 1][j - 1];
            }
        }
        return f[n1 & 1][n2];
    }
};

考点

思路