My recursive and DP java solutions with explanatory comments


  • 0
    Y

    Recursive Version:

    public class Solution {
        static public boolean isMatch(String s, String p) {
            return partialMatch(s, 0, p, 0);
        }
    
        static private boolean partialMatch(String s, int sIdx, String p, int pIdx){
            //an empty pattern only matches empty string
            if(pIdx == p.length()){
                return sIdx == s.length();
            }
    
            //pattern starts with 'x*', check if we can simply skip it and still match
            if(nextStar(p, pIdx)) {
                if (partialMatch(s, sIdx, p, pIdx + 2)) return true;
        };
    
            //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
            if(sIdx == s.length()) return false;
    
            //match first character and see if the rest matches
            if(nextStar(p, pIdx)) {
               return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx);
            }
            return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && partialMatch(s, sIdx + 1, p, pIdx+1);
        }
    
     static private boolean charMatch(char c, char p){
            return c == p || p == '.';
        }
    
        static private boolean nextStar(String p, int pIdx){
            if(pIdx + 1 >= p.length()){
                return false;
            }
            return p.charAt(pIdx+1) == '*';
        }
    
    }
    

    DP version:

    public class Solution {
    static public boolean isMatch(String s, String p) {
            boolean[][] matchMatrix = new boolean[s.length()+1][p.length()+1];
            fillMatchMatrix(s, p, matchMatrix);
            return matchMatrix[0][0];
        }
    
    
     static private void fillMatchMatrix(String s, String p, boolean[][] matchMatrix){
            for(int sIdx = s.length(); sIdx >= 0; sIdx--){
                for(int pIdx = p.length(); pIdx >= 0; pIdx--){
    		matchMatrix[sIdx][pIdx] = getMatchCellValue(s, p, matchMatrix, sIdx, pIdx);
    	}
    }
    
    static private boolean getMatchCellVaue(String s, String p, boolean[][] matchMatrix, int sIdx, int pIdx){
    	 //an empty pattern only matches empty string
            if(pIdx == p.length()) return (sIdx == s.length());
                    
    	//pattern starts with 'x*', check if we can simply skip it and still match
            if(nextStar(p, pIdx) && matchMatrix[sIdx][pIdx+2] == true) return true
    	
    	 //empty string, but cannot match the pattern by skipping the 'x*' pattern, so match fails
            if(sIdx == s.length()) return false;
    	
    	 //match first character and see if next matches
            if(nextStar(p, pIdx)){
                       return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx];
     }                  
    	return charMatch(s.charAt(sIdx), p.charAt(pIdx)) && matchMatrix[sIdx+1][pIdx+1];
    }
    
    static private boolean charMatch(char c, char p){
            return c == p || p == '.';
    }
    
    static private boolean nextStar(String p, int pIdx){
            if(pIdx + 1 >= p.length()){
                return false;
            }
            return p.charAt(pIdx+1) == '*';
        }
    
    }
    
    

Log in to reply
 

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