Short Java O(n) time, O(1) space, one pass


  • 24
    H

    The idea is to similar to validate a string only contains '(' and ')'. But extend it to tracking the lower and upper bound of valid '(' counts. My thinking process is as following.

    scan from left to right, and record counts of unpaired ‘(’ for all possible cases. For ‘(’ and ‘)’, it is straightforward, just increment and decrement all counts, respectively.
    When the character is '*', there are three cases, ‘(’, empty, or ‘)’, we can think those three cases as three branches in the ongoing route.
    Take “(**())” as an example. There are 6 chars:
    ----At step 0: only one count = 1.
    ----At step 1: the route will be diverted into three branches.
    so there are three counts: 1 - 1, 1, 1 + 1 which is 0, 1, 2, for ‘)’, empty and ‘(’ respectively.
    ----At step 2 each route is diverged into three routes again. so there will be 9 possible routes now.
    -- For count = 0, it will be diverted into 0 – 1, 0, 0 + 1, which is -1, 0, 1, but when the count is -1, that means there are more ‘)’s than ‘(’s, and we need to stop early at that route, since it is invalid. we end with 0, 1.
    -- For count = 1, it will be diverted into 1 – 1, 1, 1 + 1, which is 0, 1, 2
    -- For count = 2, it will be diverted into 2 – 1, 2, 2 + 1, which is 1, 2, 3
    To summarize step 2, we end up with counts of 0,1,2,3
    ----At step 3, increment all counts --> 1,2,3,4
    ----At step 4, decrement all counts --> 0,1,2,3
    ----At step 5, decrement all counts --> -1, 0,1,2, the route with count -1 is invalid, so stop early at that route. Now we have 0,1,2.
    In the very end, we find that there is a route that can reach count == 0. Which means all ‘(’ and ‘)’ are cancelled. So, the original String is valid.
    Another finding is counts of unpaired ‘(’ for all valid routes are consecutive integers. So we only need to keep a lower and upper bound of that consecutive integers to save space.
    One case doesn’t show up in the example is: if the upper bound is negative, that means all routes have more ‘)’ than ‘(’ --> all routes are invalid --> stop and return false.

    Hope this explanation helps.

        public boolean checkValidString(String s) {
            int low = 0;
            int high = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    low++;
                    high++;
                } else if (s.charAt(i) == ')') {
                    if (low > 0) {
                        low--;
                    }
                    high--;
                } else {
                    if (low > 0) {
                        low--;
                    }
                    high++;
                }
                if (high < 0) {
                    return false;
                }
            }
            return low == 0;
        }
    

  • 0

    Very smart solution!


  • 0
    K

    Nice elegant solution!


  • 0
    F

    Seems like a greedy solution.
    What does "solution of without *" mean?


  • 0
    C

    @fvdcx
    I think it means, the situation after replacing each of the '*' with '(' or ')'.
    Then, the lower and upper bound reflect the range of possibilities we may have with these replacements.


  • 0
    H
    This post is deleted!

  • 3
    D

    Thank you for sharing. The following is my understanding of this good idea.

    low : take '*' as ')', if there are some '(' not matched
    high : take '*' as '('

    if high < 0 means too much ')'
    if low > 0 , after the count finished, means too much '('

    since low take '*' as ')', there might be too much ')', so that low might less than 0. That's why low-- should happen only low>0. This can thought as, low only take as much as '(''s ')' and ignore other ')' s. This will not cause problem since :

    1. '*' can be treated as empty
    2. high has deal with the situation that too much ')' exist

    If there are something wrong, please let's me know. Thank you so much (^_^)


  • 0
    T

    similar idea,but your implementation is neater,
    thx for sharing


  • 0

    I think low is taking '*' as ')' and empty string , if low > 0 mean that this sub string has the number of low '(' didn't decrease, if low == 0 mean that this sub string has satisfactory.


  • 0
    J

    very smart solution. thanks for sharing


  • 0
    T

    @howei
    low is tracking minimum number of open braces
    high is tracking maximum number of open braces.

    why is there a check for low getting less than 0. why is low decremented only when it is greater than 0?


  • 0
    S

    Anybody understands what's the logic here - what is high and low and why are they being incremented or decremented the way they're in this code?


  • 0
    T

    @sha256pki
    high is tracking maximum number of open braces possible '('.
    if it encounters a *, it considers it as '('

    low is tracking minimum number of open braces.
    If it encounters a *, it considers it as ')'

    In the end, if high is negative, that means there were too many ')'

    What i don't understand is why low can't be negative?


  • 0
    H

    @topcoder4309 If low < 0, it means there are more ')' than '(', which is invalid.


  • 0
    S
    both high and low increases on '('
    both high and low decreases on ')'
    but high increases and low decreases on '*' <---- what is meaning of it? 
    
    If low is greater than zero, consider '*' as ')' and decrease it and balance '('
    Also consider it as '('  and increase high. (why?)
    
    At the end of this loop low will always be above zero, for whatever reason if low is above 0, it means '*' taken as ')' could not balance '('.
    
    My understanding - 
    
    '*' can be both '(' or ')'
    
    high - keeps track of '(' with "*" as '('
    low  - keeps track of ')' with "*" as ')'
    
    Now '*' taken as '(' is overwhelmed by ')' - then string is unbalanced - so far loop saw more ')' than '(' and '*' combined then it can never be balanced again. So if high dips below 0, return False
    
    If after taking '*' as ')' if at any point low goes below 0, then its not "definite" that string is unbalanced (probably some '*' were taken wrongly as ')').
    
    For '*' it is easy, just ignore '*'. 
    For ')' can we ignore it?
    - in a string seen so far '(' match with ')' in which case '*' seen so far ignore
    - in a string seen so far '(' are lower than '*' and ')'  in that case previously seen '*' taken as ')' to be matched with '('.

  • 0
    S

    @howei So low keeps the minimum number of UNBALANCED open braces and high keeps the maximum number of UNBALANCED open braces? Right?
    BTW, can we come up with a constant space solution for problem, i.e., "20. Valid Parentheses", using some sort of similar logic or there is no way getting rid of stack for that problem?


  • 0
    I

    @sschangi I think you can't because the other problem has 3 type of parentheses, so if you don't use some sort of stack to hold the order, you can't guarantee that the string is valid.
    e.g with ([)], if we apply the same method as in this post, we'd get a true, but actually it's invalid.


  • 0
    H

    @sschangi I think the answer from @invalid is right. Sorry, I pointed to a wrong problem of #20. What I actually mean is this problem is similar to validate a string that only has '(' and ')'.


  • 0
    S

    cool solution!


  • 0
    L

    Thanks, I had a similar thought but never thought in more details.

    Thank you.


Log in to reply
 

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