通配符匹配

为了描述方便，我们将s称为主串，p称为模式串

三种思路：

1. 贪心（超时）
2. 回溯
3. 动态规划

贪心（超时）

//
// Created by jt on 2020/8/31.
//
#include <cstring>
#include <iostream>
using namespace std;

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        return greedy(s, p, 0, 0);
    }

    bool greedy(const char *s, const char *p, int idxS, int idxP) {
        if (idxS >= strlen(s) && idxP >= strlen(p)) return true;
        if (idxS >= strlen(s) || idxP >= strlen(p)) return false;
        if (s[idxS] == p[idxP] || p[idxP] == '?') return greedy(s, p, idxS+1, idxP+1);
        if (p[idxP] == '*') {
            for (int i = idxS; i < strlen(s); ++i) {
                if (greedy(s, p, i, idxP + 1)) return true;
            }
        }
        return false;
    }
};

回溯：当模式为*时，不断延长*对主串的覆盖长度，然后继续比对剩余部分，主要逻辑如下——

1. 如果两个字符匹配或者模式串对应的字符为?时，将两个指针都加1
2. 如果模式串的字符为*时，记录*的位置以及主串的位置，将模式串指针前进一步
3. 如果字符不匹配，且模式串的字符不为*，但是记录过*的位置，将模式串指针重置为*位置的下一个位置，同时将主串的旧位置前进一步，并更新主串的位置

//
// Created by jt on 2020/8/31.
//
#include <iostream>
using namespace std;

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        const char* star=NULL;
        const char* ss=s;
        while (*s){
            // 当（两个字符匹配）或（模式串的字符为'?'）时，将两个指针同时前进一步
            // 注意p不会超出字符串的长度
            if ((*p=='?')||(*p==*s)){s++;p++;continue;}
            // 模式串的字符为'*'时，记录'*'的位置与s的位置，并且只让模式串的指针前进一步
            if (*p=='*'){star=p++; ss=s;continue;}
            // 如果当前字符不匹配，最后一个指针是'*'，当前模式指针非'*'
            // 只让模式串的指针前进一步
            if (star){ p = star+1; s=++ss;continue;}
            // 当前模式指针指向非'*'，最后一个模式串指针非'*'，且字符不匹配
            return false;
        }

        // 检查模式中剩余字符
        while (*p=='*'){p++;}

        return !*p;
    }
};

动态规划

dp[i][j]表示主串前i个字符和匹配串前j个字符的匹配结果，状态公式如下：

1. 如果s[i-1]==p[j-1] || p[j-1]=='?'，那么dp[i][j]=dp[i-1][j-1]
2. 如果p[j-1]=='*'，那么dp[i][j] = any(dp[1..i][j-1])
3. 如果s[i-1]!=p[j-1] && (p[j-1]!='*' || p[j-1]!='?')，那么dp[i][j]=false
4. 基准1: dp[0][0]=true
5. 基准2: dp[0][1..k]=true(如果p[0..k-1]中只含有*)，或dp[0][k+1..]=false(如果p[0..k-1]中只含有*，但p[k]不为*)
6. 基准3: dp[1..][0]=false

解释如下：

1. 如果当前字符匹配，那么是否匹配取决于各自子串
2. 如果模式串当前字符为*，那么是否匹配取决于主串中是否存在子串能与p[0..j-1]匹配上
3. 如果当前字符不匹配，且模式串中当前字符不为*或?，那么恒不匹配
4. 基准1: 两个空串匹配
5. 基准2: 如果主串为空且p[..]中只含有*，匹配；如果主串为空且p[..]中不仅含有*，不匹配；
6. 基准3: 如果主串非空，模式串为空，不匹配

代码如下：

//
// Created by jt on 2020/8/31.
//
#include <vector>
#include <cstring>

using namespace std;

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int sLen = strlen(s), pLen = strlen(p);
        vector<vector<bool> > dp(sLen + 1, vector<bool>(pLen + 1, true));
        for (int i = 1; i <= sLen; ++i) { dp[i][0] = false; }
        for (int i = 0; i < pLen; ++i)
            if (p[i] != '*') {
                for (int j = i + 1; j<= pLen; ++j) dp[0][j] = false;
                break;
            }
        for (int i = 1; i <= sLen; ++i) {
            for (int j = 1; j <= pLen; ++j) {
                dp[i][j] = false;
                if (s[i-1] == p[j-1] || p[j-1] == '?') dp[i][j] = dp[i-1][j-1];
                else if (p[j-1] == '*') {
                    dp[i][j] = dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                }
            }
        }
        return dp[sLen][pLen];
    }
};