A pattern-based DP solution in C++, best submission 4ms


  • 2
    class Solution {
    public:
        bool isMatch(string s, string p) 
        {
            int sLen = s.length(), pLen = p.length();
            int match[pLen+1][sLen+1];
            memset(match, 0, sizeof(int)*(pLen+1)*(sLen+1));
            match[0][0] = 1;
            for(int i = 2; i <= pLen; i += 2)
                if(p[i-1] == '*') match[i][0] = 1; else break;
            for(int i = 1; i <= pLen; ++i)
            {
                if(p[i-1] == '*')
                    for(int j = 1; j <= sLen; ++j)
                        match[i][j] = match[i-2][j] || ((p[i-2]=='.' || p[i-2]==s[j-1]) && match[i][j-1]);
                else
                    for(int j = 1; j <= sLen; ++j)
                        match[i][j] = match[i-1][j-1] && (p[i-1]=='.' || p[i-1]==s[j-1]);
            }
            return match[pLen][sLen];
        }
    };
    

  • 1

    A recursive funny solution enclosed here.

    class Solution 
    {
    private:
        bool isMatch(char* s, char* p)
        {
            if(*p == '\0') return *s == '\0';
            if(*(p+1) == '*')
                return isMatch(s, p+2) || (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, p));
            else 
                return (*s!='\0' && (*s==*p || *p=='.') && isMatch(++s, ++p));
        }
    public:
        bool isMatch(string s, string p) 
        {
            char *ss = (char*)s.c_str(), *pp = (char*)p.c_str();
            return isMatch(ss, pp);
        }
    };

  • 1

    I just have no idea why this solution is overlooked since almost all the solutions so far are just string-based.


  • 0

    @LHearen Hi LHearen, thank you for your sharing. I have a question. What does && match[i][j-1] mean in if(p[i-1] == '*')? I know match[i-2][j] means that '*' matches zero, and if '*' matches something, we need to see whether (p[i-2]=='.' || p[i-2]==s[j-1]), but why we have to add this && match[i][j-1])?


  • 0

    @zhugejunwei We have to ensure previous characters are properly matched not only just the previous one.


  • 1

    @zhugejunwei Besides we also need to refer to its previous matching state when matching one or more using *.


  • 0

    @LHearen Thanks for the explanation. Now I get it.


  • 0
    S

    @LHearen This is awesome, thanks


  • 1
    S

    @LHearen I think your recursive solution can be optimized as follows:

    class Solution {
        bool isMatch(char* s, char* p){
            if(*p == '\0') return *s == '\0';
            if(*(p+1) == '*') return isMatch(s, p+2) ||
                        (*s!='\0' && (*p=='.' || *s==*p) && isMatch(s+1, p));
            else return *s!='\0' && (*p=='.' || *s==*p) && isMatch(s+1, p+1);
        }
    public:
        bool isMatch(string s, string p) {
            return isMatch((char*)s.c_str(), (char*)p.c_str());
        }
    };
    

  • 0
    S

    @LHearen All my submissions are just gone, I just done them yesterday. What's happening?!


Log in to reply
 

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