My C++ DP solution using one-dimensional array


  • 0
    L
    class Solution {
    public:
        bool isMatch(string s, string p) {
            if (s.length() == 0 && p.length() == 0) return true;
            bool dp[p.length()];
            bool placeHolder = true;
            // init the dp value when the s is empty
            for (int i = 0; i < p.length(); i ++) {
                if (p[i] == '*') dp[i] = placeHolder;
                else dp[i] = false, placeHolder = false;
            }
            
            for (int i = 0; i < s.length(); i ++) {
                // first calculate the dp value reversely
                for (int j = p.length() - 1; j > 0; j --) {
                    if (p[j] == '*') dp[j] = dp[j - 1] || dp[j];
                    else if (p[j] == '?') dp[j] = dp[j - 1];
                    else dp[j] = dp[j - 1] && s[i] == p[j];
                }
                if (i == 0) dp[0] = p[0] == s[0] || p[0] == '?' || p[0] == '*';
                else if (p[0] != '*') dp[0] = false;
                else dp[0] = true;
                // add the value missed when using reverse calculation
                for (int j = 1; j < p.length(); j ++) {
                    if (p[j] == '*') dp[j] = dp[j - 1] || dp[j];
                }
            }
            
            return dp[p.length() - 1];
        }
    };

Log in to reply
 

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