# Very Simple DP Solution in Java

• Set up a 2-D table dp[s.length() + 1][p.length() + 1] where dp[i][j] is whether [0, i - 1] of s can be matched by [0, j - 1] of p.
dp[0][0] is true since the function returns true if both s and p are empty.
dp[0][j] refers to if an empty s can be matched by [0, j - 1] of p.
dp[i][0] refers to if [0, i - 1] of s can be matched by an empty p. All dp[i][0] values are false.

``````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 i = 1; i <= p.length(); i++) {
dp[0][i] = dp[0][i - 1] && (p.charAt(i - 1) == '*');
}

for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) != '*') {
if (p.charAt(j - 1) == '?' || (p.charAt(j - 1) == s.charAt(i - 1))) {
dp[i][j] = dp[i - 1][j - 1];
}
} else {
dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
}
}
}
return dp[s.length()][p.length()];
}
}
``````

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