Java 12 lines solution, backtracking


  • 35
    1. How to check valid parenthesis w/ only ( and )? Easy. Count each char from left to right. When we see (, count++; when we see ) count--; if count < 0, it is invalid () is more than (); At last, count should == 0.
    2. This problem added *. The easiest way is to try 3 possible ways when we see it. Return true if one of them is valid.
    class Solution {
        public boolean checkValidString(String s) {
            return check(s, 0, 0);
        }
        
        private boolean check(String s, int start, int count) {
            if (count < 0) return false;
            
            for (int i = start; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    count++;
                }
                else if (c == ')') {
                    if (count <= 0) return false;
                    count--;
                }
                else if (c == '*') {
                    return check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count);
                }
            }
            
            return count == 0;
        }
    }
    

  • 2

    When my code start have too many if else if else, next time I will remember to just attempt all possibilites at least to get solution. Thanks!


  • 0
    B

    really simple and easy to understand!!! thank you!!!


  • 2
    S

    excellent logic but TLE on python


  • 3

    @wavy This is a great observation. So, whenever we have too many if-elses, we can instead just use recursion and try out all the possibilities and return the aggregate results as applicable. Thanks for leading me to it! :)


  • 0
    S

    @shawngao This solution is O(n) time and O(n) space one. Right?


  • 1
    I

    Smart. You def realized that string size is very small so trying all possibilities is feasible.


  • 1

    @sschangi I don't think so. In worst case (string contains only *), it's like a traversal of ternary tree though we can quickly stop traversing in some ) cases. So I think the upper bond is 3^n and lower bond is 2^n, n = number of *.


  • 0
    H

    Was working on this same idea that day, time went pass like anything. couldnt solve it.. Knew it gotto be a backtracking when * comes but I was using stack instead


  • 2

    Hi @shawngao, I feel this is the easiest to understand solution. Very elegant and precise. Thanks for sharing! Below is a C++ backtracking solution using recursion with focus on simple readability, which was inspired by this Java solution. Base case is when the index equals the size of the string. This occurs when the entire string has been completely processed. When the base case is reached, if the count of remaining open parens without a corresponding close paren is equal to 0, then return true, otherwise return false. The ongoing count of open parens is continually processed for each index of the string from left-to-right. Whenever an open paren ( is found, the count of open parens is incremented by 1. Likewise, whenever a close paren ) is found, the count of open parens in decremented by 1. If the ongoing count of open parens is less than 0, then we know there are too many close parens, and return false immediately. Whenever a * occurs in the string, this is processed by checking each of 3 possibilities:

    1. the * as a ( ==> this is processed by incrementing the ongoing open count by 1: open+1
    2. the * as a ) ==> this is processed by decrementing the ongoing open count by 1: open-1
    3. the * as a ""(empty string) ==> this is processed by keeping the ongoing count of open "as is" without changing the value

    Continue processing the string for each of these possibilities. If at least one of these three possibilities results in a valid string, then return true, otherwise return false.

    class Solution{
    public:
        bool checkValidString(string s){
            return helper(s, 0, 0);
        }
        
        bool helper(const string& s, int index, int open){
            if (index==s.size()) return open==0;
    
            if (s[index]=='(')
                ++open;
            else if (s[index]==')')
                if (--open<0) return false;
            else
                return helper(s,index+1,open+1) || helper(s,index+1,open-1) || helper(s,index+1,open);
    
            return helper(s,index+1,open);
        }
    };
    

    My original solution ended up iteratively traversing the string twice (left-to-right followed by right-to-left). Originally, I didn't expect to have to traverse the string backwards, until I failed the test case "(())((())()()()(()(())())())()()((()())((()))(*". At which point, I hacked this solution to check the reverse string as well:

    https://discuss.leetcode.com/topic/104298/c-count-open-parens-from-left-to-right-then-right-to-left


  • 1
    C

    I like the way you explained, easy to understand and well thought, thanks


  • 1
    E

    I find this is the easiest and most general solution.


  • 1
    C

    Great solution and explanation.


  • 1
    N

    Awesome, thanks for sharing.


  • 0
    J

    May I ask what is the time complexity of this brilliant method?


  • 1
    J

    @claytonjwong Hi, I am confused that why we don't recursively call helper() when we encounter ( and ), and only call helper if we encounter * solely?


  • 0

    @Jiawei_Wu when an open or close parentheses is encountered, then we know for certain what they are and they cannot change. So we can process known open and close parentheses directly though the ongoing “open” count by incrementing the count for open parentheses and decrementing the count for close parentheses. However, when we reach a * wildcard, then and only then do we need to invoke helper() in order to check all different possible values for that * wildcard. The * wildcard can be considered as 1) open parentheses, 2) close parentheses, or 3) empty string. I used || Boolean OR between each helper() function call, so if at least one of those 3 possibilities results in a valid expression then the solution returns true, otherwise it returns false. Thanks, Clayton


  • 0

    @Jiawei_Wu actually I think I missed your question. The helper() function does recursively call itself even when open parentheses and close parentheses are encountered. This is done in the very last line of the helper function. The string index is incremented by 1 for each recursive call until the base case is reached. The base case occurs when we have processed the entire string and index is equal to the size of the string.

    I re-wrote my code to be more clear. Hopefully this helps...

    class Solution{
    public:
        bool checkValidString(string s){
            return helper(s,0,0);
        }
    
        bool helper(const string& s,int index,int open){
    
            if (index==s.size())
                return open==0;
    
            if (s[index]=='(')
                return helper(s,index+1,open+1);
    
            if (s[index]==')')
                return open-1 < 0 ? false : helper(s,index+1,open-1);
    
            return helper(s,index+1,open+1) || helper(s,index+1,open-1) || helper(s,index+1,open);
        }
    };
    

  • 1
    Z

    I think the worst time complexity of this solution will be O(3 ^ n), if the string is all "*". We can improved this solution by adding a 2D dp array, the worst time complexity will be improved to O(n^2). The code is as follows:

        private Boolean[][] dp;
        public boolean checkValidString(String s) {
            dp = new Boolean[s.length() + 1][s.length() + 1];
            return check(s, 0, 0);
        }
        private boolean check(String s, int start, int count) {
            if (count < 0) return false;
            int y = count;
            if (dp[start][y] != null) return dp[start][y];
            for (int i = start; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    count++;
                } else if (c == ')') {
                    if (count <= 0) return false;
                    count--;
                } else if (c == '*') {
                    dp[start][y] = (check(s, i + 1, count + 1) || check(s, i + 1, count - 1) || check(s, i + 1, count));
                    return dp[start][y];
                }
            }
            dp[start][y] = (count == 0);
            return dp[start][y];
        }
    

    Here is another version:

        private Boolean[][] dp;
        public boolean checkValidString(String s) {
            dp = new Boolean[s.length() + 1][s.length() + 1];
            return check(s, 0, 0);
        }
        private boolean check(String s, int start, int count) {
            if (count < 0) return false;
            if (start >= s.length()) return count == 0;
            int y = count;
            if (dp[start][y] != null) return dp[start][y];
            char c = s.charAt(start);
            boolean res = false;
            if (c == '(') {
                res = check(s, start + 1, count + 1);
            } else if (c == ')') {
                if (count > 0)
                    res = check(s, start + 1, count - 1);
            } else {
                res = (check(s, start + 1, count + 1) || check(s, start + 1, count - 1) || check(s, start + 1, count));
            }
            dp[start][y] = res;
            return res;
        }
    

  • 0
    J

    @shawngao Hi, May I ask why the worst case if 3 ^ n and the average time complexity is 2^n ? thanks


Log in to reply
 

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