Space complexity is O(m*n), might be optimized to O(min(m,n))

Input is assumed to be always correctly formatted, so I did not check it in my code for simplicity.

```
public boolean isMatch(String s, String p) {
boolean dp[][] = new boolean[1+s.length()][1+p.length()];
dp[0][0] = true;
// Init First Row
for (int j = 2; j < dp[0].length; j+=2) {
if (p.charAt(j-1) == '*') dp[0][j] = dp[0][j-2];
}
// First Col default to false
// Start DP here
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (s.charAt(i-1) == p.charAt(j-1) || p.charAt(j-1) == '.') {
dp[i][j] = dp[i-1][j-1];
} else if (p.charAt(j-1) == '*') {
dp[i][j] = dp[i][j-2];
if (s.charAt(i-1) == p.charAt(j-2) || p.charAt(j-2) == '.') {
dp[i][j] = dp[i][j] || dp[i-1][j];
}
}
}
}
return dp[s.length()][p.length()];
}
```