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
类似于Regular Expression Matching，会超时
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if(*s=='\0'&&*p=='\0') return true;
if(*s!='\0'&&*p=='\0') return false;
if(*s=='\0'&&*p!='\0') return false;
if(*p=='*')
{
while(*p=='*') p++;
while(*s!='\0')
{
if(isMatch(s,p)) return true;
s++;
}
return isMatch(s,p);
}
else if(*p=='?')
{
return isMatch(s+,p+);
}
else
{
return (*s==*p&&isMatch(s+,p+));
}
return false;
}
};
采用类似回溯的思想
依次对字符进行比对，如果发现p=='*'
则从（p+1）开始和s开始依次比较，如果发现不对，
则回溯到（p+1）的位置，再从s+1开始依次比较
如果再不对，则再次回溯到(p+1)的位置，从s+2位置开始依次比较
……
class Solution {
public:
bool isMatch(const char *s, const char *p) {
const char* afterStarPositionP=NULL;
const char* afterStarPositionS=NULL;
while(*s!='\0')
{
if(*s==*p||*p=='?')
{
s++;p++;
continue;
}
else if(*p=='*')
{
p++;
afterStarPositionP=p;
afterStarPositionS=s;
}
else
{
if(afterStarPositionP!=NULL)
{
afterStarPositionS++;
s=afterStarPositionS;
p=afterStarPositionP;
}
else
{
return false;
}
}
}
while(*p=='*')
{
p++;
}
if(*p=='\0') return true;
else return false;
}
};