题目:
难度: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
};