Java Solution - DP - 5ms - beats 85% - O(mXn) time & space


  • 0
     /**
      *  Reference: https://www.youtube.com/watch?v=l3hda49XcDE
      */
    
       public boolean isMatch(String str, String pattern) {
            if(null == str || null == pattern) {
                return false;
            }
            
            int lenStr = str.length();
            int lenPat = pattern.length();
            
            boolean dp[][] = new boolean[lenStr+1][lenPat+1];
            
            dp[0][0] = true;
            
            for(int i=0; i<lenPat; i++) {
                if(pattern.charAt(i) == '*') {
                    dp[0][i+1] = dp[0][i-1];
                }
            }
            
            char chStr = ' ';
            char chPat = ' ';
            
            for(int i=0; i<lenStr; i++) {
                for(int j=0; j<lenPat; j++) {
                    chStr = str.charAt(i);
                    chPat = pattern.charAt(j);
                    
                    if(chPat == chStr || chPat == '.') {
                        //check validity if chStr and chPat doesn't existed 
                        dp[i+1][j+1] = dp[i][j];
                    }
                    
                    if(chPat == '*') {
                        if(dp[i+1][j-1]) {
                            // check for 0 occurence
                            dp[i+1][j+1] = true;
                        } else if(dp[i+1][j]) {
                            // check for 1 occurence
                            dp[i+1][j+1] = true;
                        } else if(pattern.charAt(j-1) == '.' || pattern.charAt(j-1) == chStr) {
                            // check for more than 1 occurence
                            dp[i+1][j+1] = dp[i][j+1];
                        }
                    }
                }
            }
            
            return dp[lenStr][lenPat];
            
        }
    

  • 0

    Little tweak to reduce space complexity to O(n)

        public boolean isMatch(String str, String pattern) {
            if(null == str || null == pattern) {
                return false;
            }
            
            int lenStr = str.length();
            int lenPat = pattern.length();
            
            if(lenPat < 1 && lenStr <1) {
                return true;
            } else if(lenPat < 1) {
                return false;
            }
            
            boolean dp[] = new boolean[lenPat+1];
            boolean prevTop = true;
            boolean top = false;
    
            dp[0] = true;
            
            for(int j=0; j<lenPat; j++) {
                if(pattern.charAt(j) == '*') {
                    dp[j+1] = dp[j-1];
                }
            }
            
            if(lenStr < 1) {
                return dp[lenPat];
            }
            
            char chStr = ' ';
            char chPat = ' ';
            
            for(int i=0; i<lenStr; i++) {
                for(int j=0; j<lenPat; j++) {
                    chStr = str.charAt(i);
                    chPat = pattern.charAt(j);
                    
                    top = dp[j+1];
                    if(chPat == chStr || chPat == '.') {
                        //check validity if chStr and chPat doesn't existed 
                        if (j == 0) {
                            // if this is first column than be little careful
                            dp[j+1] = i==0 ? true : false;
                        } else {
                            dp[j+1] = prevTop;
                        }
                    } else if(chPat == '*') {
                        if(j > 1 && dp[j-1]) {
                            // check for 0 occurence
                            dp[j+1] = true;
                        } else if(pattern.charAt(j-1) == '.' || pattern.charAt(j-1) == chStr) {
                            // check for more than 1 occurence
                            dp[j+1] = top;
                        } else {
                             dp[j+1] = false;
                        }
                    } else {
                        dp[j+1] = false;
                    }
                    
                    prevTop = top;
                    
                }
            }
            
            return dp[lenPat];
            
        }
    

Log in to reply
 

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