Simple and Short Java solution


  • 0

    The idea is based on the well known open and close count. The only exception is that, whenever we encounter a *, we need to try all 3 possibilities that the * can take - ‘(’ or ‘)’ or ‘’

    public boolean checkValidString(String s) {
        return checkValidString(s, 0, 0, 0);
    }
    
    public boolean checkValidString(String s, int i, int open, int close) {
        if(s.length() == i) return open == close;
        if(close > open) return false;
        switch(s.charAt(i)) {
            case '(':
                return checkValidString(s, i+1, open + 1, close);
            case ')':
                return checkValidString(s, i+1, open, close + 1);
            case '*':
                return checkValidString(s, i+1, open, close) ||
                        checkValidString(s, i+1, open + 1, close) ||
                        checkValidString(s, i+1, open, close + 1);
        }
        return false;
    }
    
    

  • 0
    Z

    The same code give Time Limit Exceeded in C++ can some help me out on why this is happening.
    My C++ version of the above code

    public:
        bool checkValidity(string s,int i, int open ,int close )
        {
            if(i==s.size())
                return open == close;
            if(close > open)
                return false;
            
            switch(s[i]) {
            case '(':
                return checkValidity(s, i+1, open + 1, close);
            case ')':
                return checkValidity(s, i+1, open, close + 1);
            case '*':
                return (checkValidity(s, i+1, open, close) ||
                        checkValidity(s, i+1, open + 1, close) ||
                        checkValidity(s, i+1, open, close + 1));
            }
            
        }
        bool checkValidString(string s) {
    
            return checkValidity(s,0,0,0);
        }
    

Log in to reply
 

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