XChy's Blog

For life

0%

LeetCode 44 通配符匹配 题解

Posted on Edited on In

题目描述： img

动态规划

简单想法：

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

则有初始状态:

\[dp[0][0] = true\]

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

\[dp[i][0] = false, 0 < i \le sn\]

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

\[dp[0][j] = dp[0][j-1] \quad \wedge \quad p[j-1] = '*'\]

状态转移方程则为：

\[ \begin{equation*} %加*表示不对公式编号 \begin{split} dp[i][j] = & dp[i][j - 1] \wedge p[j - 1] = '*' \quad \vee \\ & dp[i - 1][j] \wedge p[j - 1] = '*' \quad \vee \\ & dp[i - 1][j - 1] \wedge (s[i - 1] = p[j - 1] \vee p[j - 1] = '?' \vee p[j - 1] = '*') \end{split} \end{equation*} \]

故我们可以有代码：

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
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(mn)\), 空间复杂度为 \(O(mn)\)

贪心(LeetCode 题解)

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

我们以 \(p=∗ abcd ∗\) 为例，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 * \cdots * u_x ∗\] ，即字符串（可以为空）和星号交替出现，并且首尾字符均为星号，那么我们就可以设计出下面这个基于贪心的暴力匹配算法。算法的本质是：如果在字符串 sss 中首先找到 \(u_1\) ，再找到 \(u_2, u_3, \cdots, u_x\)，那么 s 就可以与模式 p 匹配，伪代码如下：

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
36
37
38
// 我们用 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(mn)\)，平均复杂度：\(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 \(\phi\) 就是本题中的问号。

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