# Java O(n^2) dynamic programming solution

• 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:

1. If the character at `i` is `(`, then we know we must increment our count by 1, so we see if `dp[i + 1][j + 1]` is valid.

2. If the character is `)`, we will decrement our count by 1, so we see if `dp[i + 1][j - 1]` is valid.

3. If the character is `*`, now we need to check all 3 possibilities where the `*` could be `(`, `)`, or a blank character, which is represented by `dp[i + 1][j + 1]`, `dp[i + 1][j - 1]`, and `dp[i + 1][j]`. If either one of those is true, then we know `*` at index `i` can make a valid parenthesis at the given count `j`.

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];
}
}
``````

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