Java shortest DP solution


  • 13
    D
    public boolean isMatch(String s, String p) {
        boolean[] match = new boolean[s.length()+1];
        Arrays.fill(match, false);
        match[s.length()] = true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)=='*'){
                for(int j=s.length()-1;j>=0;j--)    match[j] = match[j]||match[j+1]&&(p.charAt(i-1)=='.'||s.charAt(j)==p.charAt(i-1));
                i--;
            }
            else{
                for(int j=0;j<s.length();j++)   match[j] = match[j+1]&&(p.charAt(i)=='.'||p.charAt(i)==s.charAt(j));
                match[s.length()] = false;
            }
        }
        return match[0];
    }

  • -2
    Q

    Good thinking, but throw Exception to run the case String s = "e", p = "*";


  • 0
    T

    p = "*", it is not a correct regex. there must be characters before '*'.


  • 1
    M

    Respect, that is a very neat solution. I can see that it works, but I don't fully understand why. Can you explain a little bit what the thinking is behind this algorithm?

    And what was your approach to solve this question - how did you came up with this?


  • 0
    J

    If "a**" is considered a valid regex, we can use a loop to check the "s.charAt(j)==p.charAt(i-1)" part.


  • 0
    W

    Nice solution! Also, java have default false boolean value, so you don't really need to use Arrays.fill(match, false);.


Log in to reply
 

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