4ms C++ with DP example annotate, optimised from others.


  • -2
    F
    class Solution {
    public:
        /*
        for example
        s="aab", p="c*a*b"
        the DP algorithm: (1 means true, 0 means false)
        1)
            p   c   *   a   *   b
        s
        a
        a
        b
        
        2)
            p   c   *   a   *   b
        s   1   0   1   0   1   0   <= bits
        a
        a
        b
        
        3)
            p   c   *   a   *   b
        s   1   0   1   0   1   0   <= bitsPrev
        a   0   0   0   1   1   0   <= bits
        a
        b
        
        4)
            p   c   *   a   *   b
        s   1   0   1   0   1   0
        a   0   0   0   1   1   0   <= bitsPrev
        a   0   0   0   0   1   0   <= bits
        b
        
        5)
            p   c   *   a   *   b
        s   1   0   1   0   1   0
        a   0   0   0   1   1   0
        a   0   0   0   0   1   0   <= bitsPrev
        b   0   0   0   0   0   1   <= bits
        
        the result is bits[p.length()]=1.
        */
        bool isMatch(string s, string p) {
            int plen = p.length();
            int slen = s.length();
            bool *bits = new bool[plen+1];
            bool *bitsPrev = new bool[plen+1];
            int i, j;
            char sc, pc;
            bool *tmp = NULL;
            
            /* initalize the first row bits */
            bits[0] = true;
            bits[1] = false;
            for(i=2; i<plen+1; i++) 
            {
                bits[i] = bits[i-2] && (p[i-1] == '*');
            }
            
            /* start from the second row */
            for(j=1; j<slen+1; j++)
            {
                /* set the prev row bits */
                tmp = bits; bits = bitsPrev; bitsPrev = tmp;
                
                /* set current char of s */
                sc = s[j-1];
                
                /* the first element ought to false */
                bits[0] = false;
                
                /* start from the second element */
                for(i=1; i<plen+1; i++)
                {  
                    /* set current char of p */
                    pc = p[i-1];
                    
                    /* fill in the row bits */
                    if(bitsPrev[i-1] && ((pc == '.') || (pc == sc)))
                        bits[i] = true;
                    else if((pc == '*') && (i > 1))  // actually, i won't be 1 here.
                        bits[i] = bits[i-2] || bits[i-1] || (bitsPrev[i] && (sc == p[i-2] || p[i-2] == '.'));
                    else
                        bits[i] = false;
                }
            }
            
            bool result = bits[p.size()];
            delete[] bits;
            delete[] bitsPrev;
            return result;
            
        }
    };

Log in to reply
 

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