6ms cpp dp solution


  • 0
    L
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int psize = p.size();
            int ssize = s.size();
            
            // pp : store chars without asterisk
            // star : indicate if the corresponding char is with asterisk
            string pp = "";
            vector<bool> star;
            for (int i=0; i<psize; ++i) {
                if (p[i] == '*')
                    star.back() = true;
                else {
                    star.push_back(false);
                    pp += p[i];
                }
            }
            
            psize = pp.size();
            
            // dp[i][j] means if the first i of pp matches the first j of s
            bool dp[psize+1][ssize+1];
            memset(dp, false, sizeof(dp));
            
            dp[0][0] = true;
            
            
            // the preceding chars with asterisk can match empty string
            for (int i=1; i<=psize; i++) {
                if (star[i-1] == true)
                    dp[i][0] = true;
                else
                    break;
            }
            
            for (int i=1; i<=psize; i++) {
                for (int j=1; j<=ssize; j++) {
                    // case 1:
                    if (dp[i-1][j-1] == true) {
                        if (pp[i-1] == s[j-1] || pp[i-1] == '.') {
                            dp[i][j] = true;
                            continue;
                        }
                    }
                    
                    // case 2:
                    if (dp[i-1][j] == true) {
                        if (star[i-1] == true) {
                            dp[i][j] = true;
                            continue;
                        }
                    }
                    // case 3:
                    if (dp[i][j-1] == true) {
                        if (star[i-1] == true && (pp[i-1] == s[j-1] || pp[i-1] == '.')) {
                            dp[i][j] = true;
                            continue;
                        }
                    }
                }
            }
            
            return dp[psize][ssize];
        }
    };

Log in to reply
 

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