Java solution DP with detailed explanation

• Every time you see a DP problem, you should first derive the objective function.

Here is the definition of our objective function:

``````dp[i][j] = true if s[1..i] and p[1..j] matches
``````

Let's start our derivation! First of all, we will divide the problem into three categories:

``````* p[j] = '.'
dp[i][j] = dp[i-1][j-1] since p[j] can match any s[i]

* p[j] = '*'
* in case of dp[i][j-2] is true, p[j] can used as empty character
* in case of dp[i-1][j] is true, p[j] is used to match one or more characters.
- p[j-1] == s[i]
- p[j-1] == '.'

* list itemp[j] = a-zA-Z
if dp[i-1][j-1] is true, it means that s[1..i-1] can match p[1..j-1]. we only have to check whether s[i] match p[j]

``````
``````class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0][0] = true;

for (int j = 2; j <= p.length(); j++) {
if (p.charAt(j-1) == '*' && dp[0][j-2]) {
dp[0][j] = true;
}
}

for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j-1) == '.') {
dp[i][j] = dp[i-1][j-1];
}

if (p.charAt(j-1) == '*') {
dp[i][j] = dp[i][j-2]  || dp[i-1][j] && (p.charAt(j-2) == s.charAt(i-1) || p.charAt(j-2) == '.');
}

if (s.charAt(i-1) == p.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1];
}
}
}

return dp[s.length()][p.length()];
}
}
``````

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