Classic DP c++ solution with O(MN) time and O(MN) space


  • 0
    H
    bool isMatch(string s, string p) {
        if (s == "" && p == "") return true;
        if (p == "") return false;
        int ns = (int)s.size();
        int np = (int)p.size();
        vector<vector<bool> >dp(ns+1, vector<bool>(np+1, false));
        dp[0][0] = true;
        for (int j = 1; j <= np; j++) {
            dp[0][j] = dp[0][j-1] && p[j-1] == '*';
        }
        for (int i = 1; i <= ns; i++) {
            for (int j = 1; j <= np; j++) {
                if (p[j-1] == '*') {
                    dp[i][j] = dp[i-1][j] || (dp[i][j-1]);
                } else {
                    dp[i][j] = dp[i-1][j-1] && (p[j-1] == s[i-1] || p[j-1] == '?');
                }
            }
        }
        return dp[ns][np];
    }

  • 0
    P

    Your code is very good! But I do not understand the dp process in this algorithm. Any one can help me ?


Log in to reply
 

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