题解 | #通配符匹配#

NC44 通配符匹配

题意分析：

给定字符串S，模式串P，判断S是否能够被P所匹配，通配符只有？和*，？可以匹配任意一个字符，*可以匹配任意长度的字符串

题解一（动态规划）：

设置 $dp[i][j]$ 表示字符串S的(0-i)部分是否被字符串P的(0-j)部分匹配

初始化：

$dp[0][j]$ ，字符串s的(0-0)为空，那么只要字符串P的(0-j)的部分开始为*就为true
$dp[i][0]$ ，模式串(0-0)为空，根本没发匹配， $dp[i][0]=false$
状态转移
1. 如果P[j]=="*"，并且 $dp[i-1][j]$ ==true，或者 $dp[i][j-1]$ ==true，那么 $dp[i][j]=true$
2. 如果p[j]!="*"，分两种情况
  1. 当p[j]=="?"时候，s[i]任意，并且 $dp[i-1][j-1]$ ==true时候， $dp[i][j]=true$
  2. 当p[j]==s[i]并且 $dp[i-1][j-1]$ ==true时候， $dp[i][j]=true$

举个例子：

当模式串p为空，s不匹配p，所以第一行均为F，下图红色部分

当匹配串为空。除非p以*开头，不然均为false，所以第一行红色部分为false

接下来我们按行更新：从下图的第三行开始更新

更新第三行：

当s_start = a,p_start = a时候，我们要检查他的对角处是不是T，为T则为T，否则则为false
当s_start = d,p_start = a时候，s_start和p_start均为字母，我们要检查交叉处的左边即可。字母虽然不等，当交叉处左边为T就为T
同理第一行的其他部分

更新第四行

当s_start=a，p_start=*时候，由于*可以匹配0个或多个字符，因此我们只要检查交叉处上方是否为T即可
第四行其他位置同

更新第六行

当p_start=?,s_start = a,由于？可以匹配a，那么就需要检查交叉处的左边是否为T，作为为F那么就为F。其他位置的更新同上。

图片说明
写成代码：

bool isMatch(const char *s, const char *p) {
    int m = strlen(s);
    int n = strlen(p);
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        if (p[i - 1] == '*') {
            //初始化第一列
            dp[0][i] = dp[0][i - 1];
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            //按照当前字符是否为*，
            if (p[j - 1] == '*' && (dp[i - 1][j] || dp[i][j - 1])) {
                dp[i][j] = true;
            } else {//不为*的情况
                if (p[j - 1] == '?' && dp[i - 1][j - 1]) {
                      //当为？
                    dp[i][j] = true;
                } else if (p[j - 1] == s[i - 1] && dp[i - 1][j - 1]) {
                     //当两个字符相等的时候
                    dp[i][j] = true;
                }
            }
        }
    }
    return dp[m][n];
}

时间复杂度： $O(mn)$ ，mn分别为模式串P和匹配串S的长度。

空间复杂度： $O(mn)$ 。

题解二（贪心）：

模式串中的一个？刚好可以匹配一个字符，容易处理。对于，它可以匹配任意长度的字符串，当遇到\时，可以选择忽略，或者选择匹配一定长度的字符串。我们遇到*去做贪心选择，每一次只会产生一个结果，因此，如果某次贪心错误，应该回溯到另外一个位置，然后再进行贪心选择。

我们设置两个全局变量i_start和j_start表示s和p中匹配*，初始化为-1.

变量i和j表示当前匹配的位置

如果s和p的字符发生匹配，即s[i]==s[j]或者p[j] =='?'，那么i++，j++
如果当前p[j]=="*"，这将i_start和j_start分别设置为i和j，j++
如果i_start>=0，说明有被匹配过，\可以匹配任意长度的字符串，那么就一直增加i，j跳到j_start。
当匹配结束，如果指针j没有移动到匹配串末尾，那么在p可以匹配S的情况下，p中剩余没匹配的一定是*，否则无法完全匹配。

bool isMatch(const char *s, const char *p) {
    int i = 0, j = 0, i_Star = -1, j_Star = -1;
    int m = strlen(s), n = strlen(p);
    while (i < m) {
        if (j < n && (s[i] == p[j] || p[j] == '?')) {
            i++;
            j++;
        } else if (j < n && p[j] == '*') {
            i_Star = i;
            j_Star = j;
            j++;
        } else if (i_Star >= 0) {
            i_Star++;
            i = i_Star;
            j = j_Star;
        } else {
            return false;
        }
    }
    while (j < n && p[j] == '*') {
        j++;
    }
    return j == n;
}

时间复杂度： $O(mn)$

空间复杂度： $O(1)$