算法

(DP) $O(nm)$

dp方程：

dp[i][j]表示s中前$i$个字符和p的前$j$个字符是否匹配成功，如果匹配成功则为$true$，否则为$false$

初始条件：

• s，p为空串时，能匹配成功，所以

$dp[0][0]=true$

• s为空串，p只为*时，*也能替换成空串，所以

$dp[0][i]=true$ (p串从$1$到$i$均是*号)，如果有除*号以外的字符就匹配不上了

C++ 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int sLen = s.size();
        int pLen = p.size();
        //为了空出边界条件dp[0][0] 我们dp数组从下标为1开始使用
        // dp[i][j]表示s中前i个字符和p的前j个字符是否匹配成功，如果匹配成功则为true

        vector<vector<bool> > dp(sLen + 1, vector<bool>(pLen + 1, false));
        dp[0][0] = true;

        //s为空，*也可以替换成空串，则当s为空p为连续的*号时候也是匹配成功的
        for(int i = 1; i <= pLen; i++) {
            if(p[i - 1] == '*') {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for(int i = 1; i <= sLen; i++) {
            for(int j = 1; j <= pLen; j++) {
                //p的第j个字符是*号，*号可以匹配任意串
                //所以无论是s的前i个字符和p的前j-1个字符匹配成功 将*号替换成空串
                //还是s的前i-1个字符和p的前j个字符匹配成功，*号替换的长度不限制，
                //所以可以将*号替换成的内容多加上s[i]
                // 这两种情况都能推出s的前i个字符和p的前j个字符匹配成功
                if(p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                }

                //p的第j个字符不是*号
                //如果dp[i-1][j-1]为false，
                //则s的前i-1个字符和p的前j-1个字符已经匹配失败了
                //这时候dp[i][j]只能为false了
                // 如果dp[i-1][j-1]为true，s的前i-1个字符和p的前j-1个字符已经匹配成功了
                //则要看s的第i个字符s[i] 和p的第j个字符p[j]是否匹配成功
                //s[i]和p[j]匹配成功有两种情况 1是两个字符相同，2是p[j]是？
                else {
                    if(dp[i - 1][j - 1] == true) {
                        if(s[i - 1] == p[j - 1] || p[j - 1] == '?') {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
};