# My recursive and DP java solutions with explanatory comments

• 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) == '*';
}

}

``````

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