C++ straightforward DP with pattern preprocessing


  • 0
        bool isMatch(string s, string p) {
            
            // merge consecutive *'s
            string pp; char pre = '\0';
            for (char c : p) {
                if (pre != '*' or c != '*') pp += c;
                pre = c;
            }
            p = pp;
            
            vector<int> dp(p.size()+1, 0), cur(p.size()+1, 0);
            dp[0] = 1, dp[1] = (p[0] == '*');
            
            for (int i = 1; i <= s.size(); ++i) {
                for (int j = 1; j <= p.size(); ++j) {
                    if (p[j-1] == s[i-1] or p[j-1] == '?') cur[j] = dp[j-1];
                    else if (p[j-1] == '*') cur[j]  = dp[j] or cur[j-1];
                    else cur[j] = 0; 
                }
                dp = cur;
            }
            return dp[p.size()];
        }
    

Log in to reply
 

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