Easy DP Java Solution with detailed Explanation


  • 192

    This Solution use 2D DP. beat 90% solutions, very simple.

    Here are some conditions to figure out, then the logic can be very straightforward.

    1, If p.charAt(j) == s.charAt(i) :  dp[i][j] = dp[i-1][j-1];
    2, If p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1];
    3, If p.charAt(j) == '*': 
       here are two sub conditions:
                   1   if p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2]  //in this case, a* only counts as empty
                   2   if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':
                                  dp[i][j] = dp[i-1][j]    //in this case, a* counts as multiple a 
                               or dp[i][j] = dp[i][j-1]   // in this case, a* counts as single a
                               or dp[i][j] = dp[i][j-2]   // in this case, a* counts as empty
    

    Here is the solution

    public boolean isMatch(String s, String p) {
    
        if (s == null || p == null) {
            return false;
        }
        boolean[][] dp = new boolean[s.length()+1][p.length()+1];
        dp[0][0] = true;
        for (int i = 0; i < p.length(); i++) {
            if (p.charAt(i) == '*' && dp[0][i-1]) {
                dp[0][i+1] = true;
            }
        }
        for (int i = 0 ; i < s.length(); i++) {
            for (int j = 0; j < p.length(); j++) {
                if (p.charAt(j) == '.') {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == s.charAt(i)) {
                    dp[i+1][j+1] = dp[i][j];
                }
                if (p.charAt(j) == '*') {
                    if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') {
                        dp[i+1][j+1] = dp[i+1][j-1];
                    } else {
                        dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]);
                    }
                }
            }
        }
        return dp[s.length()][p.length()];
    }

  • 4
    C

    Your logic is very concise! Nice explanation.


  • 8
    L

    Line 9: java.lang.ArrayIndexOutOfBoundsException: -1


  • 0

    I re-runs the code, it works well. When you created 2D array, its length should be s.length()+1. I think you may make a mistake here.


  • 7
    H

    so true when i == 0, dp[0][i - 1] definitely throws out an exception


  • 18
    Y

    Hi,
    in your pseudo code, in line 6.
    "p.charAt(i-1)" may give out of bound .. should it be j-1 ?


  • 3
    L

    Hi, have you tried "a" ".**" ,it doesn't accord with the expection


  • 0
    E

    for (int i = 0; i < p.length(); i++) {
    if (p.charAt(i) == '' && dp[0][i-1]) {
    dp[0][i+1] = true;
    }
    }
    While, before that code, we need to add
    if(p.charAt(0)=='
    ')
    dp[0][1]=true;

    then the pointer i should begin with 1,
    for(int i=1; i<p.length(); i++){
    ...........

    }


  • 0

    Most clearly solution I have seen


  • 38
    D

    Great explanation! But it seems that the solution code cannot be accepted. I revised your code:

    public class Solution {
        public boolean isMatch(String s, String p) {
            if(s == null || p == null) {
                return false;
            }
            boolean[][] state = new boolean[s.length() + 1][p.length() + 1];
            state[0][0] = true;
            // no need to initialize state[i][0] as false
            // initialize state[0][j]
            for (int j = 1; j < state[0].length; j++) {
                if (p.charAt(j - 1) == '*') {
                    if (state[0][j - 1] || (j > 1 && state[0][j - 2])) {
                        state[0][j] = true;
                    }
                } 
            }
            for (int i = 1; i < state.length; i++) {
                for (int j = 1; j < state[0].length; j++) {
                    if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                        state[i][j] = state[i - 1][j - 1];
                    }
                    if (p.charAt(j - 1) == '*') {
                        if (s.charAt(i - 1) != p.charAt(j - 2) && p.charAt(j - 2) != '.') {
                            state[i][j] = state[i][j - 2];
                        } else {
                            state[i][j] = state[i - 1][j] || state[i][j - 1] || state[i][j - 2];
                        }
                    }
                }
            }
            return state[s.length()][p.length()];
        }
    }
    

  • 3
    P

    @hongchang It won't reach that statement as there is one hidden assumption of the problem "the first character cannot be '*'".


  • 3

    @perfecthu Hi Perfecthu, I think in this problem the hidden assumption is * cannot be the first character.


  • 0
    S

    What if the Start of p is *, the for (int i = 0; i < p.length(); i++) should be changed to i = 1?


  • 2
    P

    @SonglianLi The start of p won't be "p" because of the hidden assumption of this problem. If there is one '*', it must follow some other character. It is not hard to find this assumption if you read the problem again.


  • 0
    A
    This post is deleted!

  • 0
    C

    @dolphinwby The code in the top post is accepted when I submitted it. And seems your solution is almost the same as the top post, but it runs faster... don't know why


  • 32

    alt text


  • 2

    @monkeyGoCrazy said in Easy DP Java Solution with detailed Explanation:

    2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':

    very nice explanation and implementation. I found in the line " 2 if p.charAt(i-1) == s.charAt(i) or p.charAt(i-1) == '.':", all the 'p.charAt(i ' should be replaced to "p.charAt( j ". please correct me if I was wrong


  • 3
    D

    Why if there's multiple same chars, dp[i][j] = dp[i-1][j]?


  • 1
    M

    @Duor Because dp is increasing from first letter to last, so if there are multiple same letters, it is still counting from first repeated to last, so the first time when we see * and the first repeated letter, we will use as single letter case, and next when we see the second letter, we will simple check if there previous is single letter case and if that is true. if the single letter matches *, it means the second is also true. And if we check the third, forth and so on it just need to take the previous results.


Log in to reply
 

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