DP C++ Solution with O(mn) time O(n) space


  • 0
    J
    class Solution {
    public:
        bool isMatch(string s, string p) {
            int m = s.length();
            int n = p.length();
            vector<bool> dp(n+1,false);
            dp[0] = true;
            bool flag = false;
            for (int j = 1; j <= n; ++j) {
                if (flag) {
                    break;
                }
                if (j < n && p[j] == '*') {
                    dp[++j] = dp[j] = true;
                } else 
                    flag = true;
            }
            for (int i = 1; i <= m; ++i) {
                bool prev = dp[0];
                dp[0] = false;
                for (int j = 1; j <= n; ++j) {
                    bool tmp = dp[j];
                    if (j < n && p[j] == '*') {
                        if (p[j-1] == '.') {
                            dp[j] = dp[j-1] || dp[j];
                        } else {
                            dp[j] = dp[j-1] || (s[i-1] == p[j-1] && dp[j]);
                        }
                        tmp = dp[j+1];
                        dp[++j] = dp[j];
                    } else  {
                        dp[j] = prev && (p[j-1]=='.' || s[i-1] == p[j-1]);
                    }
                    prev = tmp;
                }
            }
            return dp[n];
        }
    };
    

Log in to reply
 

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