题目：
难度：Hard
相关话题：贪心算法、字符串、动态规划、回溯算法
给定一个字符串( s ) 和一个字符模式( p ) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配 才算匹配成功。
说明:
示例1:
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例2:
输入:
s = "aa"
p = "*"
输出: true
解释:'*' 可以匹配任意字符串。
示例3:
输入:
s = "cb"
p = "?a"
输出: false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释:第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例5:
输入:
s = "acdcb"
p = "a*c?b"
输入: false
思路：
dp[i][j]表示前i个pattern是否能匹配前j个string。
初始dp[0][0]=true，并且如果当前p[i]是*，那么如果dp[i-1][j]为true，那么dp[i][j]也为true，因为*可以匹配空字符串。
如果遇到?或者p[i]===s[j]，说明可以匹配任意一个字符或者两者相等，检查上一次是否匹配，dp[i][j]=dp[i-1][j-1]。
如果遇到*，*可以匹配任何位数的字符，
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let pLen=p.length,sLen=s.length
let dp=Array(pLen+1).fill().map(()=>Array(sLen+1).fill(false))
dp[0][0]=true
for(let i=1;i<pLen+1;i++){
if(p[i-1]==='*' && dp[i-1][0]){
dp[i][0]=true
}
}
for(let i=1;i<pLen+1;i++){
for(let j=1;j<sLen+1;j++){
let pId=i-1,sId=j-1
if(p[pId]==="?" || p[pId]===s[sId]){
dp[i][j]=dp[i-1][j-1]
}
if(p[pId]==="*"){
dp[i][j]=dp[i-1][j] || dp[i][j-1]
}
}
}
return dp[pLen][sLen]
};
定义两个指针，pi对应pattern上的索引，si对应string上的索引，关键思想是遇到*，记录当前的位置，并不使用，等到后面无法匹配时，在去查看*的位置。
如果p[pi]===s[si] || p[pi]==="?"说明两者可以视为相等，si++和pi++；
如果p[pi]==='*'，记录当前的si和pi，继续检查；
如果不符合以上的条件，说明不匹配了，这时要回到上一次记录的*的位置，继续检查。
最后检查pi是否到达p的最后。
/**
* @来源： Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let star=-1,pi=0,si=0,match=0
while(si<s.length){
if(pi<p.length && (p[pi]===s[si] || p[pi]==="?")){
pi++
si++
}else if(pi<p.length && p[pi]==="*"){
match=si
star=pi
pi++
}else if(star!==-1){
match++
pi=star+1
si=match
}else{
return false
}
}
while(pi<p.length && p[pi]==="*"){
pi++
}
return pi===p.length
};