I used a 2d array dp[index][count]
. index
represents the index of the parenthesis string. count
represents the open/close count, where we add one for (
and subtract for )
.
The base case is dp[s.length()][0]
, which means that after we have check all of the previous characters and reach the end of the string, if the open count is 0, then that means we have found a valid parenthesis string.
Now we iterate from the end of the string to the beginning, and calculate if index i
can be a valid parenthesis at a every count j
. We look at three cases:

If the character at
i
is(
, then we know we must increment our count by 1, so we see ifdp[i + 1][j + 1]
is valid. 
If the character is
)
, we will decrement our count by 1, so we see ifdp[i + 1][j  1]
is valid. 
If the character is
*
, now we need to check all 3 possibilities where the*
could be(
,)
, or a blank character, which is represented bydp[i + 1][j + 1]
,dp[i + 1][j  1]
, anddp[i + 1][j]
. If either one of those is true, then we know*
at indexi
can make a valid parenthesis at the given countj
.
The answer will be dp[0][0]
.
class Solution {
public boolean checkValidString(String s) {
boolean[][] dp = new boolean[s.length() + 1][s.length() + 1];
dp[s.length()][0] = true;
for(int i = s.length()  1; i >= 0; i) { //index
char c = s.charAt(i);
for(int j = 0; j < s.length(); j++) {//count
if(c == '(') {
dp[i][j] = dp[i + 1][j + 1];
} else if(c == ')') {
dp[i][j] = (j == 0) ? false : dp[i + 1][j  1];
} else {
boolean open = dp[i + 1][j + 1];
boolean close = (j == 0) ? false : dp[i + 1][j  1];
boolean nothing = dp[i + 1][j];
dp[i][j] = close  open  nothing;
}
}
}
return dp[0][0];
}
}