C++, Two pass forward and back, O(n)


  • 1
    Z
    class Solution {
    public:
        bool checkValidString(string s) {
            for (int i = 0, cnt = 0, star = 0; i < n; i++) {
                if (s[i] == '(') 
                    cnt++;
                else if (s[i] == '*') 
                    star++;
                else {
                    if (cnt == 0 && star == 0) return false;
                    if (cnt) 
                        cnt--;
                    else 
                        star--;
                }
            }
            for (int i = n-1, cnt = 0, star = 0; i >= 0; i--) {
                if (s[i] == ')') 
                    cnt++;
                else if (s[i] == '*') 
                    star++;
                else {
                    if (cnt == 0 && star == 0) return false;
                    if (cnt) 
                        cnt--;
                    else 
                        star--;
                }
            }
            return true;
        }
    };
    
    

  • 1

    @zestypanda, I had the same idea, below is my C++ solution. 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 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;
        }
    };

  • 1

    Have the same idea but a python version:

    def checkValidString(self, s):
        cus, cur = 0, 0
        for i in range(len(s)):
            cus += {'(': 1, ')': -1, '*': 1}[s[i]]
            cur += {'(': -1, ')': 1, '*': 1}[s[-i-1]]
            if cus < 0  or cur < 0:
                return False
        return True

Log in to reply
 

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