判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：
- '?' 可以匹配任何单个字符。
- '*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。 - 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-1为false，
这时候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
