My 4ms C++ DP solution (another recursive version also given 72ms)


  • 20
    D

    Just to build a DP table checked, where checked[i][j] indicates whether s[0..i-1] matches with p[0..j-1]. The recursive relationship is as below:
    To match with the empty string s[0..0] (i.e. to make checked[0][j]), P[0..j-1] has to meet: p[j-1]=='*' (to cancel p[j-2]) and checked[0][j-2] == true;
    To match with the string s[0..i-1] (i.e. to make checked[i][j]), P[0..j-1] has to meet:

    1. if p[j-1] =='*', then j must be larger than 1 (j>1) and
    • checked[i][j-2] (i.e. p[j-2] cancelled by '*')
    • checked[i-1][j] && (s[i-1] ==p[j-2] || p[j-2] =='.') (s[i-1] matches with p[j-2] or '.', )
    1. if p[j-1] !='*', checked[i-1][j-1] && (s[i-1] ==p[j-1] || p[j-1] =='.')(i.e. s[i-1] matches with p[j-1] or '.')

    class Solution {

        public:
            bool isMatch(string s, string p) {
                int sSize = s.size(), pSize = p.size(), i, j;
                bool checked[sSize+1][pSize+1];
        //        fill_n(&matched[0][0], (sSize+1)*(pSize+1), false);
                
                for(j=2, checked[0][0]=true, checked[0][1]= false; j<=pSize; ++j) // match s[0..0]
                    checked[0][j] = p[j-1] == '*'? checked[0][j-2]  : false;
                for(i=1; i<=sSize; ++i)
                for(j=1, checked[i][0]=false; j<=pSize; ++j)
                {
                    if(p[j-1]=='*') // case (1)
                        checked[i][j] = (j>1) && ( checked[i][j-2]  || ( ( checked[i-1][j]) && (s[i-1]== p[j-2] || p[j-2] == '.')) );
                    else // case (2)
                        checked[i][j] = checked[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');        
                }
                return checked[sSize][pSize];
            }
        };
    

    A recursive version, divide cases into two groups (if the next p char is '*' or not)

    class Solution {
    private:
        bool helper(const string &s, const string &p, int sS, int pS)
        {
            int sSize = s.size(), pSize = p.size(), i, j; 
            if(pS==pSize) return sS ==sSize; // if p goes to its end, then only if s also goes to its end to return true;
            
            if(p[pS+1]!='*')
            {
               if( sS<sSize && (p[pS]==s[sS] || p[pS] == '.')) return helper(s, p, sS+1, pS+1);
            }
            else
            {
                if(helper(s, p, sS,pS+2)) return true;
                while(sS<sSize && (p[pS]==s[sS] || p[pS] == '.')) if(helper(s,p, ++sS, pS+2)) return true;
            }
            return false;
        }
    
    public:
        bool isMatch(string s, string p) {
           helper(s, p, 0, 0); 
        }
    };

  • 0
    Y

    For the case 1 in dp solution, there can be only two checks:

    1). (j>1) && checked[i][j-2] --when star * doesn't consume any chars in s

    2). (j>1) && checked[i-1][j] && (s[i-1]== p[j-2] || p[j-2] == '.') --when star * consume at lease one char in s


  • 0
    D

    You are right, it can be simplifed. Thanks


  • 0
    B

    why you can do this without malloc:
    bool checked[sSize+1][pSize+1];


  • 0
    D

    Your dynamic programming code fails for
    string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
    pattern a**************************************************************************************
    and similar type cases.


Log in to reply
 

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