O(n) time, O(1) space, no Recursion, just scan from left and then scan from right


  • 9
    F

    Share my accepted code.
    First scan from left, then scan from right.

        public boolean checkFromLeft(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }
            int star = 0;
            int open = 0;
            int close = 0;
            for (char c : s.toCharArray()) {
                if (c == '(') {
                    open++;
                } else if (c == ')') {
                    close++;
                } else {
                    star++;
                }
                if (close > open + star) {
                    return false;
                }
            }
            if (close == open || close - open <= star) {
                return true;
            }
            return false;
        }
        public boolean checkFromRight(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }
            int star = 0;
            int open = 0;
            int close = 0;
            for (int i = s.length() - 1; i >= 0; i--) {
                char c = s.charAt(i);
                if (c == ')') {
                    open++;
                } else if (c == '(') {
                    close++;
                } else {
                    star++;
                }
                if (close > open + star) {
                    return false;
                }
            }
            if (close == open || close - open <= star) {
                return true;
            }
            return false;
        }
        public boolean checkValidString(String s) {
            return checkFromLeft(s) && checkFromRight(s);
        }
    

  • 0
    F

    It's truly easy to understand because we just need to record the number of '(', ')' and wildcard to see if wildcard can be '(' or ')'.


  • 1

    @FionaFang, 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;
        }
    };

  • 0

    @FionaFang I wonder if you could explain why your solution is correct. I don't quite understand why your code will pass the case )( without any stars. As you can see, this is an invalid case.


  • 0

    @shurui this solution only returns true if the input value works in BOTH directions. The helper function returns true for the value )( in one direction (right-to-left). BUT the helper function returns false for the value )( in the other direction (left-to-right), therefore for the value )( this solution returns false.

    FionaFang's helper functions are invoked in this line of code:

    return checkFromLeft(s) && checkFromRight(s);
    

    My helper function is invoked in this line of code:

    return helper(s, '(', ')') && helper({s.rbegin(),s.rend()}, ')', '(');
    

  • 2
    F

    @shurui Thank you for your question.

    I ran my code under the testcase ")(", it returns false.
    It it because the following statement in each loop.

    if (close > open + star) {
        return false;
    }
    

    When we scan from left for the character ')', close = 1, open = 0, start = 0. So it breaks the code and return false.


  • 0

    @FionaFang Thanks for your explanation, I got it.


Log in to reply
 

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