A well explained dynamic programming C++ solution! 4ms!


  • 0
    M
    bool isMatch(string s, string p) {
        // Dynamic programming
        // table[i][j] tells whether s[0:i-1] and p[0:j-1] matches
        // table[0][0] = true;
        // Case 1: p[j-1] != '*', table[i][j] = (i>0) && (p[j-1] == s[i-1] || p[j-1] == '.') && table[i-1][j-1]; (p cannot match empty, i.e. i > 0)
        // Case 2: p[j-1] == '*', denote 'x' = p[j-2].
        //         Case 2.1: 'x' matches 0 times in the tail of s: table[i][j] = table[i][j-2] (omit "x*" in p);
        //         Case 2.2: 'x' matches at least 1 times in the tail of s: table[i][j] =(i > 0)&&(s[i-1] == p[j-2] || p[j-2] == '.') && table[i-1][j] (omit s[i-1] in s);
        const size_t n = s.size();
        const size_t m = p.size();
        bool table[n+1][m+1] = {0};
        table[0][0] = 1;
        for(int i = 0; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(p[j-1] != '*') table[i][j] = (i>0) && (p[j-1] == s[i-1] || p[j-1] == '.') && table[i-1][j-1];
                else table[i][j] = (table[i][j-2]) || ((i > 0)&&(s[i-1] == p[j-2] || p[j-2] == '.') && table[i-1][j]);
            }
        }
        return table[n][m];
    }

Log in to reply
 

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