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

• `````` /**
*  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];

}
``````

• 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];

}
``````

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