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


  • 0
    X

    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;
    }
    

Log in to reply
 

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