题解 | #通配符匹配#

一.题目描述
NC44通配符匹配
题目链接：https://www.nowcoder.com/practice/e96f1a44d4e44d9ab6289ee080099322tpId=196&&tqId=37075&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功，也就是字符串s可以完全转换为字符串p(题目意思有点难理解，下面给一个例子，希望读者可以看明白)
图片说明
二.算法(动态规划)
以s="adcbee"和p="a*b?b"来举例(横轴是是s,纵轴是p)

我们用dp[i][j]表示字符串s的前i个字符和模式p的前j个字符是否能匹配。
(1)如果p[i]是小写字母，那么同时对应的s[j]也必须是小写字母，状态转移方程为：dp[i][j]=dp[i-1][j-1],也就是dp[i][j]的真假和dp[i-1][j-1]的真假一样
(2)如果p[j]是问号,那么对s[i]没有任何要求，状态转移方程：dp[i][j]=dp[i-1][j-1]
(3)如果p[j]是星号，那么对s[i]更没有什么要求了，当时将会分成两种情况：
1.不使用这个星号，那么状态将从dp[i][j-1]转移过来
2.使用这个星号，那么状态将从dp[i-1][j]转移过来
状态转移方程为：dp[i][j]=dp[i][j-1]∨dp[i-1][j] ∨表示逻辑或运算
所以归纳可以得出来状态转移方程：
图片说明
状态转移方程知道了但是对于边界的处理应该注意：
1.dp[0][0]=1,s和p全为空的时候匹配成功
2.dp[i][0]=0,空模式无法匹配非空字符串
3.dp[0][j] 需要分情况讨论：因为星号才能匹配空字符串，所以只有当p的前j个字符均为星号时，dp[0][j] 才为真。

class Solution {
public:
    bool isMatch(string s, string p) {
        int dp[1005][1005];
        dp[0][0]=1;
        //对边界的初始化
        for (int i=1;i<=p.size();i++) {
            if (p[i-1]=='*') {
                dp[0][i]=true;
            } else {
                break;
            }
        }
        for (int i=1;i<=s.size();i++) {
            for (int j=1;j<=p.size();j++) {
                if (p[j-1]=='*') {//p[j]是*的状态转移
                    dp[i][j]=dp[i][j-1]|dp[i-1][j];//理解：两个状态只要有一个是true就可以实现完全匹配
                } else if (p[j-1]=='?'||s[i-1]==p[j-1]) {
                    //p[j]是问号或者p[j]和s[i]相等的时候
                    dp[i][j]=dp[i-1][j-1];
                }
            }
        }
        return dp[s.size()][p.size()];
    }
};

时间复杂度：o(nm)
空间复杂度：o(nm) 需要额外开辟二维数组
优缺点：实现简单，但是分析过程很麻烦，还需要通过表格去理解
三.算法(双指针贪心)
本题难点在于处理星号的匹配，用is和ip表示星号在s和p中匹配的位置，初始值都为-1，i和j表示当前匹配的位置，匹配过程如下：
如果s和p中字符匹配，则分别自增i和j,否则如果p中当前字符为星号，则标记is和ip，同时自增j,否则如果is>=0，表示之前匹配过星号，因为星号可以匹配任意字符串，所以继续递增i，同时移动j为ip下一个字符,否则返回false,当s中字符匹配完，p中字符不能有除星号以外字符.

class Solution {
public:
    bool isMatch(string s, string p) {
        int i=0, j=0;
        int is=-1, ip=-1;
        int m=s.size(),n=p.size();
        while (i<m) {
            if (j<n&&(s[i]==p[j]||p[j]=='?')) {
                //指针后移
                i++;
                j++;
            } else if(j<n&&p[j]=='*') {
                is=i;
                ip=j++;//指针标记
            } else if (is>= 0) {
                i=++is;
                j=ip+1;
            } else {
                return false;
            }
        }
        //把多余的星号去掉
        while (j<n&&p[j]=='*') j++;
        return j==n;
    }
};

时间复杂度：o(n)
空间复杂度：o(1) 不需要额外开辟空间
优缺点：效率不高，但是借助贪心可以方便实现