# c++ Iterative solution, Worst case T~O(MN)

• The idea is to think about string p in the form of "*xxxxx*xxxxxx*xxxxx*....*xxxx*". We go through string p, pick up current substr sandwiched by neighboring *. and try to match that sub-string in the original string s. Be noted we only have to find the first match of that sub-string in string s, unless that sub-string goes to the end of pattern string.
If no match, fail; if matched, continue to next sub-string in p.

``````bool isMatchstring s, string p)
{
int slen = s.size();
int plen = p.size();
bool result = true;

if(slen ==0 && plen == 0)
return result;
if(plen == 0)
return !result;

int strBeg = -1;
int strEnd = -1;
bool inStr = false;
int nextPosInS = 0;
for(int i=0; i<plen; i++)
{
if(p[i] == '*')
{
if(inStr)
{
inStr = false;
string newSub = p.substr(strBeg, strEnd-strBeg+1);
bool isExactBeg = (strBeg==0);
nextPosInS = MatchString(s, nextPosInS, newSub, isExactBeg, false);
if(nextPosInS < 0)
{
result = false;
break;
}
}
}
else
{
if(!inStr)
{
strBeg = i;
strEnd= i;
inStr = true;
}
else
{
strEnd = i;
}

if(i==plen-1)
{
string newSub = p.substr(strBeg, strEnd-strBeg+1);
bool isExactBeg = (strBeg==0);
nextPosInS = MatchString(s, nextPosInS, newSub, isExactBeg, true);
if(nextPosInS < 0)
{
result = false;
break;
}
}
}
}

return result;
}

int WildcardMatch::MatchString(string orig, int start, string substr, bool isExactBeg, bool isExactEnd)
{
int result = -1;
int sizeSubstr = substr.size();
int sizeOrig = orig.size();
if(sizeOrig < sizeSubstr + start)
return result;

bool match = true;
int realStart = start;
if(isExactEnd)
{
realStart = orig.size()-sizeSubstr;
if(isExactBeg && start!=realStart)
{
return result;
}
}
for(int i=realStart; i<orig.size()-sizeSubstr+1; i++)
{
int cmpd = 0;
int origd = i;
match = true;

while(cmpd < sizeSubstr)
{
if(orig[origd] != substr[cmpd] && substr[cmpd] != '?')
{
match = false;
break;
}
origd++;
cmpd++;
}
if(match)
{
result = origd;
break;
}
if(isExactBeg)
{
break;
}
}

return result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.