Java 12 lines solution, backtracking


  • 31
    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


  • 1

    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


  • 0
    C

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


  • 0
    E

    I find this is the easiest and most general solution.


  • 0
    C

    Great solution and explanation.


Log in to reply
 

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