[LeeCode]—Wildcard Matching 通配符匹配问题
Wildcard Matching
Implement wildcard pattern matching with support for '?'
and '*'
.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
本题和上一篇:
[LeetCode]—Regular Expression Matching 正则匹配 特别类似。只是“*”匹配任意字符串,不依赖于其前一个值了。
结合上一篇 Regular Expression Matching 的方法,先用递归的方式进行:
在本题的测试中,超时了。本题对时间复杂度的要求更高了。
class Solution { //递归
public:
bool isMatch(const char *s, const char *p) {
assert(s && p);
if(*p=='\0') return *s=='\0';
if(*p!='*'){
if(*p==*s || *p=='?' && *s!='\0')
return isMatch(s+1,p+1);
else
return false;
}else{
while(*s!='\0'){
if(isMatch(s,p+1))return true;
s++;
}
return isMatch(s,p+1);
}
}
};
继续学习了大牛的代码后(https://gitcafe.com/soulmachine/LeetCode)给出如下迭代法的高效代码:
主要思路:
一次性遍历s到s结束,用p模式串来匹配,看能不能将p串都匹配完(p能不能到结尾)。能匹配完(如果p剩余的是‘* ’,也作为匹配完)则说明匹配上了;否则,不能匹配。(根据能否将模式串P匹配完,作为依据)
如果p遇到非'*',二者还不匹配,只要前面‘*’出现过,那可以将s++(s进一步),p处(p不变)重新开始(不匹配的部分一笔勾销,视为上一个‘*’还在发挥作用[1])。
如果p遇到“*”,那么越过它,p++,p继续向下进一步,暂时不管它,后面如果不匹配了,它自然会发挥作用,见[1]。
class Solution{ //迭代的方法
public:
bool isMatch(const char *s,const char *p){
assert(s && p);
const char *str,*ptr;
bool star=false; //表示前面是否有*在匹配
for(str=s,ptr=p;*str!='\0';str++,ptr++){
switch(*ptr){
case '?': break;
case '*':
star=true;
s=str,p=ptr;
while(*p=='*')p++; //p停留在下一个非*处
if(p=='\0')return true;
str=s-1; //为了for自增后,依然保持当前位置
ptr=p-1; //为了for自增后,依然保持当前位置
break;
default:
if(*ptr!=*str){
if(!star)return false; //如果前面没有出现过‘*’,则匹配失败
//前面有*
s++; //目标s可以向下移动一个
str=s-1; //为了for自增后,依然保持当前位置
ptr=p-1; //为了for自增后,依然保持当前位置
}
//当*ptr==*str 匹配后 ptr,str才会自增,导致s,p向前移动一个
}
while(*ptr=='*')ptr++; //如果ptr剩余的值是*,那么视为P匹配结束了,所以进行此步处理
return (*ptr=='\0');
}
};
还有人使用Greedy方法,将* 作为一个分隔符,将P串以*为间隔分块,然后在字符串里看是否这些块按顺序出现的办法。
http://blog.csdn.net/magisu/article/details/17020173