9-lines 16ms C++ DP Solutions with Explanations


  • 79

    This problem has a typical solution using Dynamic Programming. We define the state P[i][j] to be true if s[0..i) matches p[0..j) and false otherwise. Then the state equations are:

    1. P[i][j] = P[i - 1][j - 1], if p[j - 1] != '*' && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
    2. P[i][j] = P[i][j - 2], if p[j - 1] == '*' and the pattern repeats for 0 times;
    3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'), if p[j - 1] == '*' and the pattern repeats for at least 1 times.

    Putting these together, we will have the following code.

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

  • 1
    R

    Can you give some explanations on following code:

        for(int j = 1; j <= n; j++) 
            dp[0][j] = (j > 1 && p.charAt(j-1) == '*' && dp[0][j-2]);
    

  • 7
    T

    Thank you for your solution!
    By the way, you may merge the two "for" loops into one.

    class Solution {
    public:
        bool isMatch(string s, string p) {
            // dynamic programming
            int m=s.length(), n = p.length();
            vector<vector<bool>> dp (m+1, vector<bool> (n+1, false));
            // initial state
            dp[0][0] = true;
            for(int i = 0; i < m+1; i++) {
                for(int j = 1; j < n+1; j++) {
                    if(p[j-1] != '*') {
                        dp[i][j] = i > 0 && dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.');
                    }
                    else {
                        dp[i][j] = dp[i][j-2] || (i > 0 && dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')); 
                    }
                }
            }
            return dp[m][n];
        }
    };

  • 1

    Hi, readman. dp[0][j] simply means whether p[0..j) matches the empty string (s[0..0) is an empty string). For a string to match an empty string, the string has to end with *, otherwise the string will have at least one character and thus cannot be matched. For example, "a*b*c*" can match "", just by setting the appearances of all a, b and c to 0. Morever, if a string say, p, matches the empty string, then p followed by any pattern like "a*" will also match the empty string. The above code just checks for this.

    Well, after the remind by Toxic. The two parts are merged now :-)


  • 1

    Hi, Toxic. Thank you for your improvements. The code becomes cleaner now :-)


  • 0
    R

    Thanks! that helps a lot


  • 0
    D

    Hi,man.when your p is begin whith *,eg:s= aa,p= *a,your program has a bug,it will shutdown by accident!


  • 1

    Hi, DGuco. You are right. But it is unreasonable for p to begin with a * since * means "Matches zero or more of the preceding element". If * is the first letter, it has preceding letter and how to match zero or more of nothing?


  • 0
    C

    @jianchao.li.fighter, I think dp[0][j] simply means whether p[0..j) (not s[0..j)) matches the empty string (s[0..0) is an empty string). right?


  • 0

    Hi, @caikehe. Yeah, you're right :-) I've updated the above answer.


  • 0
    M

    I still have a doubt..
    when the loop is iterating for the first time, then the value of the "i " is 0 and j = 1;
    Then if we will try to check the conditions like: dp[ i ] [ j - 2 ], then why it will not throw the error array out of bound!!! Am I missing something silly!!


  • 0

    Because before checking dp[i][j-2], we check p[j-1] == '*' first and no string will start with a *.


  • 0
    M

    Ohh!! Thanks for the quick response. I did know it cannot start from "*".

    I have one more doubt...
    Can we optimize this solution, as if get any "false" in between the loop, then the RegEx will result in "false" for sure.. So, we can perform a quick check if dp[i][j] is false then we can return the result from the loop!!!


  • 0

    Really amazing. I could not think how you can have this code without debugging because the assignment is so complex. BTW. I think you can only use two vectors, instead of m+1.


  • -2

    As you see, Your DP solution can not pass the case:

       s="aa"
       p="*"
    

    Please check your code . Because the problem does not say the input is valid and the input can not start with "*"


  • 1

    The problem does say!!!

    * Matches zero or more of the preceding element.

    If * is the first element, then which is its preceding element?


  • 0

    What I mean is that no one can ensure your input is in the right format.


  • 1

    The problem does ensure...


  • 0

    why it does not work if we use rolling array to further optimize the solution?
    boolean dp = new boolean[2][n + 1]

    then replace [i] with [i % 2] ?


  • 0

    So is it an assumption that the input will be always valid, so we will never have things like "*" or "" as pattern?


Log in to reply
 

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