http://oj.leetcode.com/problems/wildcard-matching/
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Note: The Solution object is instantiated only once and is reused by each test case.
while(p[0]!='*'&&p[0]!=0)
{
if(s[0]==0)
return false;
if(p[0]==s[0]||p[0]=='?')
{
p++;s++;
}
else
return false;
}
if(s[0]==0&&p[0]==0)
return true;
while(p[0]!=0&&p[1]=='*') p++;
if(s[0]==0&&p[0]=='*'&&p[1]==0)
return true;
if(s[0]==0||p[0]==0)
return false;
char pattern[100][2000]; int size=0; const char * sadP=p;
while(p[0]!='\0')
{
while(p[0]=='*') p++;
if(p[0]=='\0') break;
int tmp=0;
while(p[0]!='*'&&p[0]!=0)
{
pattern[size][tmp++]=p[0];
p++;
}
pattern[size][tmp]=0; size++;
}
if(size==0) return true;
if(*(p-1)=='*')
pattern[size++][0]='*';
for(int i=0;i<size-1;++i)
{
const char * nextP=0;
if( f(s,pattern[i],nextP) )
{
s=nextP;
continue;
}
else
{
return false;
}
}
if(pattern[size-1][0]=='*')
return true;
int remain=0;
while(s[0]!=0){ s++;remain++;}
if(sadP[0]!='*'&&size==1&&remain!=strlen(pattern[size-1]))
return false;
if(remain<strlen(pattern[size-1]))
return false;
s-=strlen(pattern[size-1]);
int tmp=0;
while(s[0]!=0&&(s[0]==pattern[size-1][tmp])||(pattern[size-1][tmp]=='?'))
{
s++;tmp++;
}
if(s[0]==0)
return true;
else
return false;
}
bool f(const char * s, const char * pattern, const char * & nextP)
{
const char * start1=s,* start2=pattern,* aux=s;
while(aux[0]!=0&&pattern[0]!=0)
{
while((aux[0]==pattern[0]||pattern[0]=='?')&&pattern[0]!=0&&aux[0]!=0)
{
aux++;pattern++;
}
if(pattern[0])
{
aux=++start1;
pattern=start2;
}
}
if(pattern[0]!=0)
return false;
nextP=aux;
return true;
}
};