3ms C++ Dynamic Solution


  • 0
    R
        bool isMatch(string s, string p) {
            int n = s.length(), m=p.length();
            bool d[n+5][m+5];
            
            d[0][0] = true;
            for (int i=1; i<=n; ++i)
                d[i][0] = false;
            for (int j=1; j<=m; ++j){
                if (j > 1 && p[j-1] == '*')
                    d[0][j] = d[0][j-2];
                else
                    d[0][j] = false;
            }
            
            for (int i=1; i<=n; ++i)
                for (int j=1; j<=m; ++j){
                    if (p[j-1] == '*')
                        d[i][j] = d[i][j-2] | (((s[i-1] == p[j-2]) | (p[j-2] == '.')) & d[i-1][j]);
                    else
                        d[i][j] = d[i-1][j-1] & ((s[i-1] == p[j-1]) | (p[j-1] == '.'));
                }
            
            return d[n][m];
        }
    

Log in to reply
 

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