Simple recursive solution in Java

  • 0
    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;

  • 0

    Doesn't this have exponential time complexity?

Log in to reply

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