recurrence idea: for mark all the possible number of net '(' as true for the first `i`

characters. At the end, check if net zero "(" is possible. On the way, cases with negative number of net '(' (i.e., some ')' appears before its closing ')') are not considered or marked. So later combinations depending on negative number of net '('s will not be true.

```
public boolean checkValidString(String s) {
if (s.length() == 0) {
return true;
}
boolean[][] mem = new boolean[s.length()][s.length() + 1];
char first = s.charAt(0);
if (first == '(') {
mem[0][1] = true;
} else if (first == ')') {
return false;
} else {
mem[0][0] = true;
mem[0][1] = true;
}
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
for (int j = i + 1; j >= 0; j--) {
if (c == ')') {
if (j <= i) {
mem[i][j] = mem[i - 1][j + 1];
}
} else if (c == '(') {
if (j > 0) {
mem[i][j] = mem[i - 1][j - 1];
}
} else {
mem[i][j] = (j <= i ? mem[i - 1][j + 1] : false) || (j > 0 ? mem[i - 1][j - 1] : false) || mem[i - 1][j];
}
}
}
return mem[s.length() - 1][0];
}
```