My Java DP Solution


  • 18
    J

    At first I cannot pass the the long 'aaa...' test case. Then I add more check and pass it.

    public class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length(), n = p.length();
            int count = 0;
            for (int i = 0; i < n; i++) {
                if (p.charAt(i) == '*') count++;
            }
            if (count==0 && m != n) return false;
            else if (n - count > m) return false;
            
            boolean[] match = new boolean[m+1];
            match[0] = true;
            for (int i = 0; i < m; i++) {
                match[i+1] = false;
            }
            for (int i = 0; i < n; i++) {
                if (p.charAt(i) == '*') {
                    for (int j = 0; j < m; j++) {
                        match[j+1] = match[j] || match[j+1]; 
                    }
                } else {
                    for (int j = m-1; j >= 0; j--) {
                        match[j+1] = (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j)) && match[j];
                    }
                    match[0] = false;
                }
            }
            return match[m];
        }
    }

  • 0
    R

    I am a little confused about the last for loop. It seems the algorithm will return true for matching "ab" and "bb", because int the last for loop matching the last letter will write true to match[m]


  • 0
    R

    Sorry, never mind. The browser cuts the right side of the code


  • 0
    Z

    nice solution and very readable


  • 1
    L

    I guess for (int i = 0; i < m; i++) { match[i+1] = false; } is redundant because default value is already false ?


  • 4
    M

    Great! Thanks for sharing. In the else condition, why should it make

    match[0] = false;
    

    And your DP solution is much faster than the top viewed C++ DP solution. Rewrite it in C++.

    bool isMatch(string s, string p) {  //DP
            int m = s.length(), n = p.length();
            int count = 0;
            for(int i=0; i<n; i++){
                if(p[i]=='*') count++;
            }
            if((count==0 && m!=n) || (n-count>m))return false;
            
            bool *match = new bool[m+1]{};
            match[0]=true;
            
            for (int i = 0; i < n; i++) {
               if(p[i]=='*'){
                   for(int j=1; j<=m; j++){
                       match[j] = match[j-1] || match[j];
                   }
               }
               else{
                   for(int j=m; j>0; j--){
                       match[j] = (p[i]=='?' || p[i]==s[j-1]) && match[j-1];
                   }
                   match[0]=false;
               }
            }
            return match[m];
        }

  • 0
    K
    This post is deleted!

  • 0
    S

    The solution I favor most for this question!


  • 0
    A

    can you add some explanation? I can't understand, thank you


  • 0
    H

    "else if (n - count > m) return false;"

    The above solution will not work for "aaaa" and "***a"


  • 0

    Some explanation would be nice. The algorithm is difficult to understand.


  • 0

    Beautiful solution! Spend three days to understand.
    If you want to understand this solution, please first try the DP solution with space O(mn).


  • 0
    J

    what match[0] means here, and why we change match[0]=false; when p[i] is not *?
    Thanks


  • 3

    My Java DP solution:

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

    }


Log in to reply
 

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