Key idea is to keep tracking the number of "(" and ")", if, at any time, the number of right parenthesis is greater than the number of left parenthesis, return false.

When "*" is find, treat it as "(" or ")" or empty string. When the String s is traversed, simply check if number of left parenthesis is equal to the number or right parenthesis or not.

```
class Solution {
public boolean checkValidString(String s) {
if (s == null || s.length() == 0) return true;
return helper(s, 0, 0, 0);
}
private boolean helper(String s, int left, int right, int pos) {
if (right > left) return false;
for (int i = pos; i < s.length(); i++) {
if (s.charAt(i) == '(') {
left++;
}
else if (s.charAt(i) == ')') {
right++;
if (right > left) return false;
}
else {
if (helper(s, left + 1, right, i + 1)) return true;
else if (helper(s, left, right + 1, i + 1)) return true;
else if (helper(s, left, right, i + 1)) return true;
else return false;
}
}
return left == right;
}
}
```