C++ count open parens from left-to-right, then right-to-left


  • 0

    Scanning the input string from left-to-right, the helper function tracks the count of open parens through the int open. The count of open parens should always be >= 0, otherwise, there are too many close parens found during the input string scanning. The exception to this rule is if there are wildcards: *. If there is a *, then it could be used as an open paren. If there is an insufficient amount of * for this exception, then we end up with too many close parens, and the string is invalid, so we return false immediately when there are more close parens than open parens + wildcards.

    Once finished scanning the input string, the amount of open parens must be less than or equal to the amount of wildcards. (Since the wildcards would be used as close parens in order to make the string valid.) If this is true, then we return true, otherwise if the amount of open parens is greater than the amount of wildcards, then we return false.

    This same scanning technique is used in the reverse order in order to catch false positives such as "(())((())()()()(()(())())())()()((()())((()))(*".

    class Solution{
    public:
        bool checkValidString(string s){
            return helper(s, '(', ')') && helper({s.rbegin(),s.rend()}, ')', '(');
        }
        
        bool helper(const string& s, const char& beg, const char& end){
            int open=0, wildcard=0;
            int i=0;
            for (auto& ch : s){
                if(ch==beg){++open;} else if(ch==end){--open;} else{++wildcard;}
                if(open < 0 && wildcard < -open){
                    return false;
                }
            }
            return open <= wildcard ? true : false;
        }
    };

Log in to reply
 

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