C++ single array DP beats 55%


  • 0
    D
    class Solution {
       public:
        bool isMatch(string s, string p) {
            const int n = s.size(), m = p.size();
            int cnt = count(p.begin(), p.end(), '*');
            // https://discuss.leetcode.com/topic/10794/my-java-dp-solution
            if ((cnt == 0 && m != n) || (m - cnt > n)) return false;
            bool dp[m + 1];
            fill_n(&dp[0], m + 1, false);
    
            // when s is empty, dp[i] is true iff p is empty or all the way "*"
            dp[0] = true;
            for (int i = 1; i <= m; ++i) dp[i] = (p[i - 1] == '*' && dp[i - 1]);
    
            for (int i = 1; i <= n; ++i) {
                bool prev = dp[0];
                dp[0] = false;
                for (int j = 1; j <= m; ++j) {
                    int temp = dp[j];
                    dp[j] =
                        p[j - 1] == '*'
                            ? (prev || dp[j - 1] || temp)
                            : ((p[j - 1] == '?' || s[i - 1] == p[j - 1]) && prev);
                    prev = temp;
                }
            }
            return dp[m];
        }
    };
    

Log in to reply
 

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