Sharing my 44ms DP code O(mn) time and O(n) space


  • 2
    C
    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            int n = (int)strlen(s), m = (int)strlen(p);
            if(m == 0) {
                return n == 0;
            }
            vector<bool> dp(n + 1, false);
            dp[0] = true;
            for (int i = 1; i <= m; i++) {
                if(i < m && p[i] == '*') {
                    for (int k = 0; k < n; k++) {
                        dp[k + 1] = dp[k + 1] || (dp[k] && (p[i - 1] == '.' || p[i - 1] == s[k]));
                    }
                    i++;
                } else {
                    for (int j = n; j > 0; j--) {
                        dp[j] = dp[j - 1] && (p[i - 1] == '.' || s[j - 1] == p[i - 1]);
                    }
                }
                dp[0] = dp[0] && p[i - 1] == '*';
            }
            return dp[n];
        }
    };
    

    I use a vector of size n + 1 to store the current progress as for each step only the previous step result is needed to calculate the current step, if we just iterate the array from the back end we can store them in the same array.


  • 0
    S

    hi~ I like your answer. it really simplifies mine a lot.


Log in to reply
 

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