Concise and easy to understand C++ iterative dp solution with explanations.


  • 0
    Z

    The state dp[i][j] denote whether s[0:i) and p[0:j) match.
    We then have 5 equations:

    1. When regex p is empty, it matches no string, except an empty one.
    2. When string s is empty, it matches regex that has the repetitive pattern which has pairs of any character other than * and followed by a , e.g. "a* b*" or ".* x* z*"
    3. If current char in s and p matches, or current char in p is a ".", dp[i][j] reduces to subproblem dp[i-1][j-1];
    4. If current char in the p is *, and the char before it matches the current char in s or is a ".", dp[i][j] is true if dp[i-1][j-1] just like in 3, or dp[i-1][j] is true, this accounts for a * matching multiple repeated characters.
    5. Finally, on top of above formulas, if current char in p is a *, dp[i][j] is true if any of dp[i][j-1] or dp[i][j-2] is true. This accounts for the fact that * expressions in the regex can be skipped safely.

    Feel free to suggest improvement or ask a question. :)

    class Solution {

    public:

    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1));
        dp[0][0] = true;
        int k = 1, cnt = 0;
        while (k < n && p[k] == '*') {
            cnt++;
            k += 2;
        }
        for (int i = 1; i <= cnt; i++)
            dp[0][2*i] = true;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++) {
                if (s[i-1] == p[j-1] || p[j-1] == '.')
                    dp[i][j] = dp[i-1][j-1];
                else if (p[j-1] == '*' && (p[j-2] == s[i-1] | p[j-2] =='.'))
                    dp[i][j] = dp[i-1][j-1] | dp[i-1][j];
                if (p[j-1] == '*')
                    dp[i][j] =  dp[i][j] | dp[i][j-1] | dp[i][j-2];
            }
        return dp[m][n];
    }
    

    };


Log in to reply
 

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