题目:
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
输入:
s = "acdcb"
p = "a*c?b"
输出: false
这题和之前的一道正则表达式匹配很相似 留下链接:day-20:正则表达式匹配 (难度:困难)
看下两题的不同点:
感觉之后可以把相似的题目归到一起,先做个TODO待之后有时间弄吧
变量声明:
,存放位置s[i]
,存放位置p[j]
特殊情况:
指针切换时的逻辑判断:
等于
,那匹配的结果和上一次一样dp[i-1][j-1],即上一次匹配成功就沿用成功失败就沿用失败
等于'?','?'可以转换成
,则那匹配的结果也和上一次一样dp[i-1][j-1]
等于'*':
与
比较的结果
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
if (s == null || p == null) return false
let len1 = s.length,
len2 = p.length
let dp = new Array(len1 + 1)
for (let i = 0; i < dp.length; i++) dp[i] = new Array(len2 + 1).fill(false);
dp[0][0] = true
for (let j = 1; j < len2+1; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = true;
}
else {
break;
}
}
for (let i = 1; i < len1 + 1; ++i) {
for (let j = 1; j <= len2; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
else if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[len1][len2];
};
):
实现
先对s和p倒序匹配:
再对s和p正序(分割)匹配:
变量声明:
起始位置的设定:
则无法准确获得, 则默认sRecord=0,pRecord=-1,标记
开始
模式p分割
形式说明:
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let sRight = s.length,
pRight = p.length;
// s和p倒序匹配
// p 的最后一个字符是星号,那么 s 未匹配完,那么没有关系
// 如果 p 没有匹配完,那么 p 剩余的字符必须都是星号
while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
--sRight;
--pRight;
} else {
return false;
}
}
if (pRight == 0) {
return sRight == 0;
}
let sIndex = 0,
pIndex = 0;
let sRecord = -1,
pRecord = -1;
// s和p正序(分割)匹配
while (sIndex < sRight && pIndex < pRight) {
// 遇到'*',说明找到了 u_x,开始寻找 u_x+1
if (p.charAt(pIndex) == '*') {
++pIndex;
// 更新p和s的起始位置
sRecord = sIndex;
pRecord = pIndex;
} else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
// 如果匹配,就继续寻找 u_x 的下一个字符
++sIndex;
++pIndex;
} else if (sRecord != -1 && sRecord + 1 < sRight) {
// 如果不匹配,那么需要重新寻找 u_x
++sRecord;
sIndex = sRecord;
pIndex = pRecord;
} else {
// 如果不匹配并且下一个起始位置不存在,那么匹配失败
return false;
}
}
// 匹配所有能匹配的u_x,如果还剩余包含'*'的无效u_x则说明匹配失败
return allStars(p, pIndex, pRight);
// 分割u_x,指定位置区间中包含'*'则说明是无效的u_x
function allStars(str,left,right) {
for (let i = left; i < right; ++i) {
if (str.charAt(i) != '*') {
return false;
}
}
return true;
}
// 单个字符匹配
function charMatch(u,v) {
return u == v || v == '?';
}
};
得到'*'匹配的长度:
未匹配完成的标记为,在下个'*'之前的字母已匹配不上
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function (s, p) {
let sIndex = 0,
pIndex = 0,
sLen = s.length,
pLen = p.length,
sRecord = -1, // 上一次出现'*'对应的s的位置(sIndex),默认为-1
pRecord = -1, // 上一次出现'*'对应的p的位置(pIndex)
matches = 0; // '*'匹配的字符个数,默认为0
// 遍历目标字符串
while (sIndex < sLen) {
// 如果遇到正常字符或者‘?’,两个指针直接递增
if (pIndex < pLen && (s[sIndex] === p[pIndex] || p[pIndex] === '?')) {
pIndex++
sIndex++
} else if (pIndex < pLen && p[pIndex] === '*') {
matches = 0
// 遇到了'*',记录此时对应的目标字符串的指针
sRecord = sIndex
// 记录此时p的指针
pRecord = pIndex
// p指针后移一位
pIndex++
} else if (sRecord !== -1) {
// 如果在下一个'*' 出现前p的'?'和字符还没匹配完(pRecord到p[pIndex] === '*')
// 则 '*'代表的字母增加一个,回溯开始位置重新匹配
matches++
sIndex = sRecord + matches
pIndex = pRecord + 1
} else {
return false
}
}
// 判断此时是否还有‘*’没有遍历完
while (pIndex < pLen && p[pIndex] === '*') {
pIndex++
}
return pIndex === pLen
}
优化:减少中间计数变量(matches)
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let sIndex = 0,
pIndex = 0,
sRecord = -1,
pRecord = -1;
while (sIndex < s.length) {
// 如果遇到正常字符或者‘?’,两个指针直接递增
if (pIndex < p.length && (s[sIndex] === p[pIndex] || p[pIndex] === '?')) {
sIndex++,
pIndex++;
} else if (pIndex < p.length && p[pIndex] === '*') {
// 遇到了'*',记录此时对应的目标字符串的指针
// 记录如果之后序列匹配不成功时, sIndex和pIndex需要回溯到的位置
sRecord = sIndex;
pRecord = pIndex++;
} else if (pRecord > -1) {
// 发现当前字符不匹配且没有星号 但是 pRecord > -1
// 说明可能是 * 之前匹配的字符数量少了 这时回溯,让*匹配的字符增加一个
sIndex = ++sRecord;
pIndex = pRecord + 1;
} else {
return false;
}
}
//如果 p 中还有多余的字符的话,那必须都是 * 否则 匹配就不成功
while (pIndex < p.length) if (p[pIndex++] !== '*') return false;
return true;
};
思路与上面记录匹配数量基本一致
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let cache = [-1,-1],
slen = s.length,
plen = p.length,
pIndex = 0,
sIndex = 0;
while(sIndex<slen){
if(pIndex < plen && (p[pIndex] ==s[sIndex]||p[pIndex] =='*'||p[pIndex] == '?')){
// 存储'*'要匹配的开始位置
if(p[pIndex] == '*'){
cache[0] = pIndex
cache[1] = sIndex
} else {
sIndex += 1
}
pIndex += 1
} else if (cache[0] != -1) {
// '*'分割的字符串未完成匹配,'*'替换的字符数增加一个试试
pIndex = cache[0] + 1
sIndex = cache[1] + 1
cache[1] += 1
} else {
// 如果某个'*'分割的区间没有匹配完说明整个字符串都是不可能匹配的
return false
}
}
while(pIndex<plen && p[pIndex]=="*") {
pIndex +=1
}
return (pIndex == plen)
};
最后,最近用码云搭了个文档的站点,刷题的内容每天也会同步到上面,感兴趣可以点击原文链接看下,感谢关注。