LeetCode 44 通配符匹配题解

题目描述：

动态规划

简单想法：

使用动态规划，令 $d p [i] [j]$ 为 是否 $s [0. . i]$ 与 $p [0. . j]$ 匹配 ,也就是 s 前 i 个字符与 p 前 j 个字符匹配。

则有初始状态:

$d p [0] [0] = t r u e$

由于长度大于 0 的字符串不可能被长度为 0 的模式匹配，故令：

$d p [i] [0] = f a l s e, 0 < i \leq s n$

同时长度为 0 的字符串只可能被形如"*"这样全为通配符的模式匹配，故令：

$d p [0] [j] = d p [0] [j - 1] \land p [j - 1] =^{'} *^{'}$

状态转移方程则为：

$\begin{aligned} d p [i] [j] = & d p [i] [j - 1] \land p [j - 1] =^{'} *^{'} \lor \\ d p [i - 1] [j] \land p [j - 1] =^{'} *^{'} \lor \\ d p [i - 1] [j - 1] \land (s [i - 1] = p [j - 1] \lor p [j - 1] =^{'} ?^{'} \lor p [j - 1] =^{'} *^{'}) \end{aligned}$

故我们可以有代码：

bool dp[2001][2001];

class Solution {
public:
  bool isMatch(string s, string p) {
    if (s.length() == 0 &&
        std::all_of(p.begin(), p.end(), [](char c) { return c == '*'; }))
      return true;
    if (p.length() == 0)
      return false;

    int sn = s.length();
    int pn = p.length();
    dp[0][0] = 1;
    for (int i = 1; i <= pn; ++i) {
      dp[0][i] = std::all_of(p.begin(), p.begin() + i,
                             [](char c) { return c == '*'; });
    }
    for (int i = 1; i <= sn; ++i) {
      dp[i][0] = false;
    }
    for (int i = 1; i <= sn; ++i) {
      for (int j = 1; j <= pn; ++j) {

        bool a = dp[i][j] =
            (dp[i][j - 1] && p[j - 1] == '*') ||
            (dp[i - 1][j] && p[j - 1] == '*') ||
            (dp[i - 1][j - 1] &&
             (s[i - 1] == p[j - 1] || p[j - 1] == '?' || p[j - 1] == '*'));
      }
    }
    return dp[sn][pn];
  }
};

时间复杂度为 $O (m n)$ , 空间复杂度为 $O (m n)$

贪心(LeetCode 题解)

前一方法的瓶颈在于对星号 $*$ 的处理方式：使用动态规划枚举所有的情况。由于星号是「万能」的匹配字符，连续的多个星号和单个星号实际上是等价的，那么不连续的多个星号呢？

我们以 $p = * a b c d *$ 为例，ppp 可以匹配所有包含子串 abcd 的字符串，也就是说，我们只需要暴力地枚举字符串 s 中的每个位置作为起始位置，并判断对应的子串是否为 abcd 即可。这种暴力方法的时间复杂度为 O(mn)，与动态规划一致，但不需要额外的空间。

如果 p=∗abcd∗efgh∗i∗ 呢？显然，ppp 可以匹配所有依次出现子串 abcd、efgh、i 的字符串。此时，对于任意一个字符串 sss，我们首先暴力找到最早出现的 abcd，随后从下一个位置开始暴力找到最早出现的 efgh，最后找出 i，就可以判断 sss 是否可以与 ppp 匹配。这样「贪心地」找到最早出现的子串是比较直观的，因为如果 sss 中多次出现了某个子串，那么我们选择最早出现的位置，可以使得后续子串能被找到的机会更大。

因此，如果模式 ppp 的形式为 $* u_{1} * u_{2} * u_{3} * \dots * u_{x} *$ ，即字符串（可以为空）和星号交替出现，并且首尾字符均为星号，那么我们就可以设计出下面这个基于贪心的暴力匹配算法。算法的本质是：如果在字符串 sss 中首先找到 $u_{1}$ ，再找到 $u_{2}, u_{3}, \dots, u_{x}$ ，那么 s 就可以与模式 p 匹配，伪代码如下：

// 我们用 sIndex 和 pIndex 表示当前遍历到 s 和 p 的位置
// 此时我们正在 s 中寻找某个 u_i
// 其在 s 和 p 中的起始位置为 sRecord 和 pRecord

// sIndex 和 sRecord 的初始值为 0
// 即我们从字符串 s 的首位开始匹配
sIndex = sRecord = 0

// pIndex 和 pRecord 的初始值为 1
// 这是因为模式 p 的首位是星号，那么 u_1 的起始位置为 1
pIndex = pRecord = 1

while sIndex < s.length and pIndex < p.length do
    if p[pIndex] == '*' then
        // 如果遇到星号，说明找到了 u_i，开始寻找 u_i+1
        pIndex += 1
        // 记录下起始位置
        sRecord = sIndex
        pRecord = pIndex
    else if match(s[sIndex], p[pIndex]) then
        // 如果两个字符可以匹配，就继续寻找 u_i 的下一个字符
        sIndex += 1
        pIndex += 1
    else if sRecord + 1 < s.length then
        // 如果两个字符不匹配，那么需要重新寻找 u_i
        // 枚举下一个 s 中的起始位置
        sRecord += 1
        sIndex = sRecord
        pIndex = pRecord
    else
        // 如果不匹配并且下一个起始位置不存在，那么匹配失败
        return False
    end if
end while

// 由于 p 的最后一个字符是星号，那么 s 未匹配完，那么没有关系
// 但如果 p 没有匹配完，那么 p 剩余的字符必须都是星号
return all(p[pIndex] ~ p[p.length - 1] == '*')

当然还有一些特殊情况，如星号不总是出现在前后，此处省略。时间复杂度：渐进： $O (m n)$ ，平均复杂度： $O (m \log n)$ 具体的分析可以参考论文On the Average-case Complexity of Pattern Matching with Wildcards，注意论文中的分析是对于每一个 $u_{i}$ 而言的，即模式中只包含小写字母和问号，本题相当于多个连续模式的情况。由于超出了面试难度。这里不再赘述。

空间复杂度：O(1)

此外(LeetCode 官方题解)

在贪心方法中，对于每一个被星号分隔的、只包含小写字符和问号的子模式 $u_{i}$ ，我们在原串中使用的是暴力匹配的方法。然而这里是可以继续进行优化的，即使用 AC 自动机代替暴力方法进行匹配。由于 AC 自动机本身已经是竞赛难度的知识点，而本题还需要在 AC 自动机中额外存储一些内容才能完成匹配，因此这种做法远远超过了面试难度。这里只给出参考讲义 Set Matching and Aho-Corasick Algorithm：

讲义的前 6 页介绍了字典树 Trie；
讲义的 7−19 页介绍了 AC 自动机，它是以字典树为基础的；
讲义的 20−23 页介绍了基于 AC 自动机的一种 wildcard matching 算法，其中的 wildcard $ϕ$ 就是本题中的问号。

感兴趣的读者可以尝试进行学习。