# Simple recursive solution in Java

• ``````class Solution {
public boolean checkValidString(String s) {
int len = s.length();
if(len==0) return true;
return recurse(s, 0, 0, 0);
}

// open: number of open parenthesis used so far
// close: number of close parenthesis used so far
public boolean recurse(String s, int idx, int open, int close) {
int len = s.length();

// if number of open parenthesis used are same as number of close parenthesis,
// it is a valid permutation
if(idx==len && open==close) return true;

if(idx>=len) return false;

// if at any point number of close parenthesis used are greater than open, return false
if(close > open) return false;

char ch = s.charAt(idx);
if(ch=='(') {
// used 1 open parenthesis
return recurse(s, idx+1, open+1, close);
}
if(ch==')') {
// used 1 close parenthesis
return recurse(s, idx+1, open, close+1);
}
if(ch=='*') {
// three choices, '(' or ')' or empty string
boolean c2 = recurse(s, idx+1, open+1, close);
boolean c3 = recurse(s, idx+1, open, close+1);
boolean c1 = recurse(s, idx+1, open, close);

return c1||c2||c3;
}

// control will reach here only if character in string is neither of '(', ')', '*'
return false;
}
}
``````

• Doesn't this have exponential time complexity?

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