通配符匹配你了解吗

通配符匹配

问题描述

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

示例：

输入: s = "adceb" p = "*a*b"

输出: true

解释: 第一个 ‘*’ 可以匹配空字符串, 第二个 ‘*’ 可以匹配字符串 “dce”。

分析问题

根据题意，给定的模式串p中，只有三种类型的字符出现，即小写字母a~z，问号 ‘?’ 和星号 ‘*’，其中 ‘小写字母’ 和 ‘问号’ 的匹配是确定的，即小写字母a~z只能匹配与之对应的小写字母，问号 ‘?’ 可以匹配任意一个小写字母；而星号的匹配是不确定的，它可以匹配零到任意多个小写字母，因此需要枚举所有可能匹配的情况。为了减少重复情况，我们可以使用动态规划来求解。

我们用dp[i] [j] 表示字符串s的前i个字符和模式串p的前j个字符是否能匹配。下面我们来看一下如何求状态转移方程。

对于模式串 p 的第 j 个字符 p_j 和 字符串s的第 i 个字符 s_i 的匹配过程如下。

1. 如果 p_j 是小写字母，要想dp[i] [j]为真，那么 s_i 必须和 p_j 相同，否则为假。即状态转移方程为

   dp[i] [j] = (s_i==p_j ) and dp[i-1] [j-1]

​ 即要想dp[i] [j]为真，当且仅当 si==pj 为True，并且dp[i-1] [j-1] 也为True。

1. 如果 p_j 是问号‘？’，那么对 s_i 没有任何要求，即状态转移方程为：

   dp[i] [j] = dp[i-1] [j-1]

2. 如果 p_j 是星号‘* ’，那么对 s_i 没有任何要求，但是星号可以匹配零到任意多个小写字母，因此状态转移方程分为两种情况。

   • 如果星号表示多个字符，我们把该星号留着，即j不动，i-1，如果dp[i-1] [j]能匹配，则dp[i] [j] 也能匹配，因为星号 ‘*’ 可以表示任意字符，所以当前i-1加上一个字符后的i也就能匹配。所以dp[i] [j] = dp[i-1] [j]
   • 如果星号表示的是空字符，则保持i不动，j-1，如果dp[i] [j-1]能匹配，则dp[i] [j]也能匹配，即dp[i] [j] = dp[i] [j-1]

综上所述，最终的状态转移方程如下所示:

​ dp[i] [j] =$$\begin{cases} dp[i-1] [j-1] ， 当si == pj 或者pj 是问号时 \\ dp[i-1] [j] 或者 dp[i] [j-1]，当pj时星号时\\False，其它情况 \end{cases}$$

下面我们来看一下边界条件。

• dp[0] [0]=True，即当字符串s和模式串p都为空时，表示匹配成功。
• dp[i] [0] = False，即当模式串p为空时，它是不能匹配任意非空字符串的，所以为False。
• dp[0] [j] 是需要分情况来看的，因为只有星号‘’才能匹配空字符串，所以只有当模式串前j个字符都是星号‘ ’时，dp[0] [j] 才为真。

下面我们来看一个具体的例子，这里先说明一点，因为字符串的下标从 0 开始，所以下图中si 和 pj 分别对应着 s[i-1]和 p[j-1]。

对于字符串s = "adceb"，p = "*a*b" 来说。首先，我们先初始化边界条件，如下图所示。

下面我们来看一下代码的实现。

class Solution:
    def isMatch(self, s, p):
        #求出字符串的长度
        m, n = len(s), len(p)
        #创建状态转移矩阵
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        #初始化边界条件
        dp[0][0] = True
        #如果pj的前j个字符都是'*'，表示可以匹配空
        #字符串s,所以dp[0][j]=true
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = True
            else:
                break

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                #如果pj=='*',那么dp[i][j]=dp[i][j - 1] or dp[i - 1][j]
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                # 如果pj=='?'或者si==pj
                # 那么dp[i][j]=dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] == '?' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]

        return dp[m][n]

该算法的时间复杂度是O(m n)，空间复杂度也是O(m n)。其中 m 和 n 分别是字符串 s 和模式串 p 的长度。