判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

• '?' 可以匹配任何单个字符。
• '*' 可以匹配任意字符串（包括空字符串）。
  两个串完全匹配才算匹配成功。
• 1<=|s|, |p| <= 1000
• s仅包含小写英文字母
• p包含小写英文字母，？和 *

在线评测地址：领扣题库官网

样例1

输入:
"aa"
"a"
输出: false

输出2

输入:
"aa"
"aa"
输出: true

输出3

输入:
"aa"
"*"
输出: true
说明: '*' 可以替换任何字符串

样例4

输入:
"ab"
"?*"
输出: true
说明: '?' -> 'a' '*' -> 'b'

算法：动态规划
dp方程
dpi表示s中前i个字符和p的前j个字符是否匹配成功，如果匹配成功则为true，否则为false
初始条件

• s，p为空串时 能匹配成功 所以dp0=true
• s为空串，p只为号时候，号也能替换成空串，所以dp0=true (p串从1到i均是号)，如果有除号以外的字符就匹配不上了
  方程转移

对于dpi

• p的第j个字符是号，号可以匹配任意串

  • 所以无论是s的前i个字符和p的前j-1个字符匹配成功 将*号替换成空串
  • 还是s的前i-1个字符和p的前j个字符匹配成功，*号替换的长度不限制，
    所以可以将*号替换成的内容多加上s[i]

这两种情况都能推出s的前i个字符和p的前j个字符匹配成功
if(p[j-1]=='*') {
dpi = dpi-1 || dpi;
}

• p的第j个字符不是*号

  • 如果dpi-1为false，
    则s的前i-1个字符和p的前j-1个字符已经匹配失败了

这时候dpi只能为false了

• 如果dpi-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(dpi-1 == true) {

    if(s[i-1]==p[j-1] || p[j-1]=='?'){
        dp[i][j]=true;
    }

}
}

注意事项

我们dp数组下标为0的地方要表示空串的答案，所以dpi是s串的前i个字符和p串前j个字符，这里的i和j的记数不是从0开始的
复杂度分析
时间复杂度
dp数组状态是O(NM)的，转移是O(1)的
所以总时间复杂度是O(NM)的
N是s串长度，M是p串长度
空间复杂度
dp数组空间O(NM)
代码

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

        //初始化dp数组
        boolean [][]dp = new boolean[sLen + 5][pLen + 5];
        for(int i = 0; i <= sLen; i++) {
            for(int j = 0; j <= pLen; j++) {
                dp[i][j] = false;
            }
        }
        dp[0][0] = true;

        //s为空，*也可以替换成空串，则当s为空p为连续的*号时候也是匹配成功的
        for(int i = 1; i <= pLen; i++) {
            if(p.charAt(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.charAt(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.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[sLen][pLen];

    }
}

更多题解参考：九章官网solution