Quite intuitive and efficient solution O(n) DP in C, well-commented


  • 1

    Basic DP version

    bool isMatch0(char* s, char* p)
    {
        int sLen=strlen(s), pLen=strlen(p);
        int** match=(int**)malloc(sizeof(int*)*(sLen+1));
        for(int i = 0; i < sLen+1; i++)
        {
            match[i] = (int*)malloc(sizeof(int)*(pLen+1));
            memset(match[i], 0, sizeof(int)*(pLen+1));
        }
        match[0][0] = true;
        for(int i = 0; i < sLen+1; i++) //start index should be zero;
        {
            for(int j = 1; j < pLen+1; j++)
            {
                if(p[j-1] != '*')
                    match[i][j] = i && match[i-1][j-1] && (p[j-1]=='.' || p[j-1]==s[i-1]);
                else
                    match[i][j] = (j>1 && match[i][j-2]) ||  //match zero in s;
                    (i && match[i-1][j] && (p[j-2]=='.'||p[j-2]==s[i-1])); //match one or more;
            }
        }
        return match[sLen][pLen];
    }
    

    linear space cost DP version

    //AC - 4ms;
    bool isMatch(char* s, char* p)
    {
        int sLen = strlen(s), pLen = strlen(p);
        bool *pre = (bool*)malloc(sizeof(bool)*(pLen+1));
        bool *cur = (bool*)malloc(sizeof(bool)*(pLen+1));
        memset(pre, 0, sizeof(bool)*(pLen+1));
        memset(cur, 0, sizeof(bool)*(pLen+1));
        pre[0] = cur[0] = true;
        for(int i=0; i <= sLen; i++)
        {
            if(i) cur[0]=false; //string is not empty, so pattern cannot be empty;
            for(int j=1; j <= pLen; j++)
            {
                char c=*(p+j-1); //adjust the index for better coding;
                if(c != '*')
                    cur[j] = i>0 && pre[j-1] && (c=='.' || c==*(s+i-1));
                else
                    //two different situations: match zero or not zero letters in s;
                    cur[j] = (j>1 && cur[j-2]) ||  //matching zero;
                        (i>0 && pre[j] && (*(p+j-2)=='.' || *(p+j-2) == *(s+i-1))); //matching one or more - be careful about the index here;
            }
            bool *t = pre; pre = cur, cur = t;
        }
        return pre[pLen];
    }

  • 1

    The recursive solution should be enclosed here, quite intuitive!


    bool isMatch(char *s, char* p)
    {
        if(*p == '\0') return *s=='\0';
        if(*(p+1) == '*')
            return isMatch(s, p+2) ||  //match zero letter in s;
                (*s!='\0' && (*s==*p || '.'==*p) && isMatch(++s, p)); //match one or more;
        else
            return *s!='\0' && (*s==*p || '.'==*p) && isMatch(++s, ++p);
    }

  • 0
    P

    Pretty clean solution, thanks for detailed comments.


  • 0
    P

    I liked this solution as well, pretty clean.


  • 0
    P

    what would be complexity?


  • 0

    As for the DP solution it's quite straight-forward O(pLen*sLen), when it comes to the recursive one the worst case will be O(2^sLen) but the best O(sLen), the average will be O(2^n) n is determined by the structure of the string s and p both.


  • 0
    I

    if *s == "" and *p == ".*abc", it will be stackoverflow...
    Maybe return isMatch(s, p+2) || (*s != '\0' && (*s==*p || '.'==*p) && isMatch(++s, p)) would be appropriate.


  • 0

    Thanks for your testing and carefulness, that's a good shot! The previous OJ just let it pass, the case you mentioned is quite correct, my bad! I've updated it already, thanks again for your sharing!


Log in to reply
 

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